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)

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