On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract

DOI10.1137/1.9781611975482.59zbMath1434.05137arXiv1611.02460OpenAlexW2907355031MaRDI QIDQ5236243

Thomas Sauerwald, Frederik Mallmann-Trenn, Varun Kanade

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.02460

zbMATH Keywords

coalescing random walkscouplingmeeting timereversible Markov chainharmonic mean formula

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Related Items (13)

A stochastic process on a network with connections to Laplacian systems of equations ⋮ Reversible random walks on dynamic graphs ⋮ Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models ⋮ Voter models on subcritical scale‐free random graphs ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ On the meeting of random walks on random DFA ⋮ Biased opinion dynamics: when the devil is in the details ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two-type annihilating systems on the complete and star graph ⋮ Coalescing and branching simple symmetric exclusion process ⋮ Mean field behavior during the big bang regime for coalescing random walks

This page was built for publication: On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract