Coalescing Random Walks and Voting on Connected Graphs

DOI10.1137/120900368zbMath1361.05120arXiv1204.4106OpenAlexW2963594409MaRDI QIDQ5408589

Robert Elsässer, Colin Cooper, Hirotaka Ono, Tomasz Radzik

Publication date: 10 April 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random walkscoalescing random walksvoter model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Related Items (19)

Coalescing Walks on Rotor-Router Systems ⋮ Voter and majority dynamics with biased and stubborn agents ⋮ Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs ⋮ Random walks and diffusion on networks ⋮ Reversible random walks on dynamic graphs ⋮ Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ 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 ⋮ Inverse Problems for Discrete Heat Equations and Random Walks for a Class of Graphs ⋮ Probabilistic consensus via polling and majority rules ⋮ Electrical networks with prescribed current and applications to random walks on graphs ⋮ Game-based coalescence in multi-agent systems ⋮ Reaching consensus on a connected graph ⋮ Discordant Voting Processes on Finite Graphs ⋮ Two-type annihilating systems on the complete and star graph ⋮ Discordant voting protocols for cyclically linked agents ⋮ Mean field behavior during the big bang regime for coalescing random walks

This page was built for publication: Coalescing Random Walks and Voting on Connected Graphs