Rumor Spreading with No Dependence on Conductance
From MaRDI portal
Publication:2963582
DOI10.1137/14099992XzbMath1359.68024OpenAlexW2583780251MaRDI QIDQ2963582
Jonathan A. Kelner, Petar Maymounkov, Keren Censor-Hillel, Bernhard Haeupler
Publication date: 15 February 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/14099992x
Network design and communication in computer systems (68M10) Distributed systems (68M14) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bound of the Hadwiger number of graphs by their average degree
- Forests, frames, and games: Algorithms for matroid sums and applications
- Sublinear fully distributed partition with applications
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Almost tight bounds for rumour spreading with conductance
- Asynchronous Rumor Spreading in Preferential Attachment Graphs
- Low distortion spanners
- On the locality of distributed sparse spanner construction
- Asymptotically Optimal Randomized Rumor Spreading
- Quasirandom Rumor Spreading on the Complete Graph Is as Fast as Randomized Rumor Spreading
- Spectral Sparsification of Graphs
- Additive spanners and (α, β)-spanners
- Fully dynamic randomized algorithms for graph spanners
- Randomized broadcast in networks
- Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
- Graph spanners
- Distributed Computing: A Locality-Sensitive Approach
- An Optimal Synchronizer for the Hypercube
- Spatial gossip and resource location protocols
- Computing separable functions via gossip
- Tight Bounds for Rumor Spreading with Vertex Expansion
- Asynchronous gossip
- Global computation in a poorly connected world
- Social networks spread rumors in sublogarithmic time
- Simple, Fast and Deterministic Gossip and Rumor Spreading
- Distributed algorithms for ultrasparse spanners and linear size skeletons
