Collisions Among Random Walks on a Graph
From MaRDI portal
Publication:3136609
DOI10.1137/0406029zbMath0776.60083OpenAlexW1964535518MaRDI QIDQ3136609
Peter M. Winkler, Don Coppersmith, Prasad Tetali
Publication date: 14 October 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406029
Extremal problems in graph theory (05C35) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Lipschitz embeddings of random fields ⋮ Unnamed Item ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ The infection time of graphs ⋮ TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS ⋮ Exact mixing times for random walks on trees ⋮ Clairvoyant scheduling of random walks ⋮ Hitting time quasi-metric and its forest representation ⋮ Collecting coupons on trees, and the cover time of random walks ⋮ A tight lower bound on the cover time for random walks on graphs ⋮ The end time of SIS epidemics driven by random walks on edge-transitive graphs ⋮ Some remarks on cops and drunk robbers ⋮ An Extension of Foster's Network Theorem ⋮ Lipschitz embeddings of random sequences ⋮ Avoidance couplings on non‐complete graphs ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Capturing the drunk robber on a graph ⋮ A tight upper bound on the cover time for random walks on graphs ⋮ A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents ⋮ A Hitting Time Formula for the Discrete Green's Function ⋮ Monotonicity of Avoidance Coupling on KN ⋮ Hitting Times, Cover Cost, and the Wiener Index of a Tree ⋮ Some bounds for the Kirchhoff index of graphs ⋮ Faster Treasure Hunt and Better Strongly Universal Exploration Sequences ⋮ How to meet in anonymous network ⋮ Scheduling of Non-Colliding Random Walks ⋮ Random walks on a complete graph: a model for infection ⋮ Exit Frequency Matrices for Finite Markov Chains ⋮ Random walks and flights over connected graphs and complex networks ⋮ On a Form of Coordinate Percolation ⋮ An Algorithmic Theory of Mobile Agents ⋮ Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences ⋮ The maximum relaxation time of a random walk ⋮ The hitting and cover times of random walks on finite graphs using local degree information ⋮ Exact computation for meeting times and infection times of random walks on graphs ⋮ Efficient distributed computation of distance sketches in networks ⋮ An Upper Bound on the Size of Avoidance Couplings ⋮ Percolation of Words on Zd with Long-Range Connections ⋮ Improved approximation of the minimum cover time ⋮ On the expected time for Herman's probabilistic self-stabilizing algorithm
