Coalescing random walks and voting on graphs

DOI10.1145/2332432.2332440MaRDI QIDQ2933775zbMATH OpenOpenAlexFDO

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

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2332432.2332440

zbMATH Keywords

random walksdistributed voting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Random walks on graphs (05C81) Voting theory (91B12) Distributed systems (68M14)

Recommendations

• Coalescing random walks and voting on connected graphs
• Coalescent random walks on graphs
• Coalescing random walk on unimodular graphs
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Tight bounds for coalescing-branching random walks on regular graphs
• Random walks on graphs: ideas, techniques and results
• Random walks on dense graphs and graphons
• scientific article; zbMATH DE number 4197088
• Random Walks on Randomly Evolving Graphs

Cited in

(25)

• A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence
• Meeting, coalescence and consensus time on random directed graphs
• Interacting particle systems as stochastic social dynamics
• Dispersion processes
• Voting protocols on the star graph
• Biased opinion dynamics: when the devil is in the details
• Asynchronous opinion dynamics in social networks
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Brief Announcement: Discrete Incremental Voting
• Distributed Averaging in Opinion Dynamics
• Reaching consensus on a connected graph
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Coalescent random walks on graphs
• Site recurrence for coalescing random walk
• Tight bounds for coalescing-branching random walks on regular graphs
• Discordant Voting Processes on Finite Graphs
• The coalescing-branching random walk on expanders and the dual epidemic process
• Stochastic coalescence in logarithmic time
• Stochastic coalescence in logarithmic time
• Fast consensus for voting on general expander graphs
• Coalescing random walks and voting on connected graphs
• Coalescence and meeting times on \(n\)-block Markov chains
• Coalescing random walk on unimodular graphs
• On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
• Threshold behaviour of discordant voting on the complete graph

This page was built for publication: Coalescing random walks and voting on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933775)