Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
P. Berenbrink,George Giakkoupis,Peter Kling
2018 · DOI: 10.1137/1.9781611975031.112
ACM-SIAM Symposium on Discrete Algorithms · 15 Citations
TLDR
A bound of O (p−1 log n) rounds with high probability on the cover time of a CoBra walk with k = 2 on any regular graph with n nodes and conductance p is shown, which improves upon all previous bounds in terms of graph expansion parameters.