On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
From MaRDI portal
Publication:6075753
DOI10.1145/3576900OpenAlexW2556309115WikidataQ130981295 ScholiaQ130981295MaRDI QIDQ6075753
Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3576900
Cites Work
- Mean field conditions for coalescing random walks
- Mixing times are hitting times of large sets
- Tight bounds for the cover time of multiple random walks
- Meeting times for independent Markov chains
- Chernoff-type bound for finite Markov chains
- Local majorities, coalitions and monopolies in graphs: A review
- Fast consensus for voting on general expander graphs
- Bounds on the cover time
- Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
- Distributed probabilistic polling and applications to proportionate agreement
- Collisions of random walks
- Multiple Random Walks in Random Regular Graphs
- Collisions Among Random Walks on a Graph
- Tight bounds for asynchronous randomized consensus
- Multiple Random Walks and Interacting Particle Systems
- How Well Do Random Walks Parallelize?
- Stabilizing Consensus with Many Opinions
- Bounds on the Voter Model in Dynamic Networks
- Testing Expansion in Bounded-Degree Graphs
- The Power of Two Choices in Distributed Voting
- Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
- Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
- Many Random Walks Are Faster Than One
- Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
- The Cover Time of Random Regular Graphs
- Plurality Consensus in the Gossip Model
- Ignore or Comply?
- On the coalescence time of reversible random walks
- Coalescing Random Walks and Voting on Connected Graphs
- On the Laplacian Eigenvalues of Gn,p
This page was built for publication: On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
