Meeting times of random walks on graphs

DOI10.1016/S0020-0190(99)00017-4zbMATH Open1338.68213MaRDI QIDQ294672FDOQ294672

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

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

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

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)

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 (9)

• The no-meet matroid
• Collisions Among Random Walks on a Graph
• A cops and robber game and the meeting time of synchronous directed walks
• Meeting times of random walks on graphs
• Randomized uniform self-stabilizing mutual exclusion
• Exact computation for meeting times and infection times of random walks on graphs
• The survival of the weakest in networks
• Quantized consensus in Hamiltonian graphs
• Title not available (Why is that?)

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)