Flooding time in edge-Markovian dynamic graphs
DOI10.1145/1400751.1400781zbMATH Open1301.05308OpenAlexW2013558775MaRDI QIDQ2934348FDOQ2934348
Authors: Claudio Macci, Angelo Monti, Francesco Pasquale, Andrea Clementi, Riccardo Silvestri 
Publication date: 12 December 2014
Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1400751.1400781
Recommendations
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Network design and communication in computer systems (68M10)
Cited In (57)
- Effects of concurrency on epidemic spreading in Markovian temporal networks
- Sharp Thresholds in Random Simple Temporal Graphs
- Distributed Community Detection in Dynamic Graphs
- Resilience of mutual exclusion algorithms to transient memory faults
- Byzantine agreement with homonyms
- Adaptively secure broadcast, revisited
- Continuous-time independent edge-Markovian random graph process
- Distributed deterministic edge coloring using bounded neighborhood independence
- Compact policy routing
- Coordinated consensus in dynamic networks
- The space complexity of long-lived and one-shot timestamp implementations
- Traveling salesman problems in temporal graphs
- Parsimonious flooding in dynamic graphs
- MIS on trees
- Distributed graph coloring in a few rounds
- Cover time in edge-uniform stochastically-evolving graphs
- Time-efficient randomized multiple-message broadcast in radio networks
- From bounded to unbounded concurrency objects and back
- Upper and lower bounds for the synchronizer performance in systems with probabilistic message loss
- Xheal, localized self-healing using expanders
- Evaluating the impact of selfish behaviors on epidemic forwarding in mobile social networks
- Toward more localized local algorithms, removing assumptions concerning global knowledge
- Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
- Temporal network epidemiology
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
- Locally checkable proofs
- Discovery through gossip
- Optimal-time adaptive strong renaming, with applications to counting
- Analyzing consistency properties for fun and profit
- Stability of a peer-to-peer communication system
- The impact of memory models on software reliability in multiprocessors
- A tight unconditional lower bound on distributed randomwalk computation
- Scalable rational secret sharing
- Information spreading in dynamic networks: an analytical approach
- Parsimonious flooding in geometric random-walks
- Structuring unreliable radio networks
- Error-free multi-valued consensus with Byzantine failures
- Information spreading in dynamic graphs
- An introduction to temporal graphs: an algorithmic perspective
- An introduction to temporal graphs: an algorithmic perspective
- Minimum congestion mapping in a cloud
- Conflict on a communication channel
- The round complexity of distributed sorting, extended abstract
- Distributed community detection in dynamic graphs
- Temporal network optimization subject to connectivity constraints
- Rumor spreading in random evolving graphs
- Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
- Flooding time of edge-Markovian evolving graphs
- Order optimal information spreading using algebraic gossip
- Fast and compact self stabilizing verification, computation, and fault detection of an MST
- A complexity separation between the cache-coherent and distributed shared memory models
- The complexity of robust atomic storage
- Parsimonious flooding in dynamic graphs
- Fault-tolerant spanners
- Parsimonious flooding in geometric random-walks (extended abstract)
- Faster information dissemination in dynamic networks via network coding
- Tight bounds on information dissemination in sparse mobile networks
This page was built for publication: Flooding time in edge-Markovian dynamic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934348)
