Meeting times of random walks on graphs

DOI10.1016/S0020-0190(99)00017-4MaRDI QIDQ294672zbMATH OpenFDO

Authors Nader H. Bshouty, Lisa Higham, Jolanta Warpechowska-Gruca

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019099000174?np=y

zbMATH Keywords

distributed computinganalysis of algorithmshitting timerandom walksmeeting time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Random walks on graphs (05C81)

Recommendations

• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Exact computation for meeting times and infection times of random walks on graphs
• On the cover time of random walks on graphs
• Collisions Among Random Walks on a Graph
• Multiple lazy random walks on cycles

Cites work

• Meeting times for independent Markov chains
• Meeting times of random walks on graphs
• On a random walk problem arising in self-stabilizing token management

Cited in

(16)

• The no-meet matroid
• On the meeting of random walks on random DFA
• Meeting times of random walks on graphs
• Randomized uniform self-stabilizing mutual exclusion
• Collisions Among Random Walks on a Graph
• A cops and robber game and the meeting time of synchronous directed walks
• Exact computation for meeting times and infection times of random walks on graphs
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Merging time of random mobile agents
• The survival of the weakest in networks
• On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
• Multiple lazy random walks on cycles
• Quantized consensus in Hamiltonian graphs
• Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
• scientific article; zbMATH DE number 524141 (Why is no real title available?)
• About the distance between random walkers on some graphs

This page was built for publication: Meeting times of random walks on graphs

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