Collisions Among Random Walks on a Graph

DOI10.1137/0406029MaRDI QIDQ3136609zbMATHOpenAlexFDO

Authors Don Coppersmith, Peter Winkler, 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

zbMATH Keywords

Markov chainrandom walkpotential functionself-stabilizing systemstoken management

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Sums of independent random variables; random walks (60G50)

Recommendations

• Meeting times of random walks on graphs
• scientific article; zbMATH DE number 524141
• scientific article; zbMATH DE number 878897
• Recurrence and collisions of random walks

Cited in

(49)

• Lipschitz embeddings of random fields
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents
• scientific article; zbMATH DE number 524141 (Why is no real title available?)
• Percolation of Words on Z^d with Long-Range Connections
• A hitting time formula for the discrete Green's function
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• Scheduling of non-colliding random walks
• Collecting coupons on trees, and the cover time of random walks
• Hitting time quasi-metric and its forest representation
• An Algorithmic Theory of Mobile Agents
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• Capturing the drunk robber on a graph
• On the meeting of random walks on random DFA
• Lipschitz embeddings of random sequences
• Random walks with the minimum degree local rule have \(O(n^2)\) cover time
• Random walks and flights over connected graphs and complex networks
• Exact computation for meeting times and infection times of random walks on graphs
• Avoidance coupling
• Efficient distributed computation of distance sketches in networks
• The infection time of graphs
• The hitting and cover times of random walks on finite graphs using local degree information
• scientific article; zbMATH DE number 5896696 (Why is no real title available?)
• Clairvoyant scheduling of random walks
• A tight lower bound on the cover time for random walks on graphs
• Recurrence and collisions of random walks
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• The maximum relaxation time of a random walk
• How to meet in anonymous network
• Improved approximation of the minimum cover time
• Collisions of several walkers in recurrent random environments
• On a Form of Coordinate Percolation
• Hitting times, cover cost, and the Wiener index of a tree
• A tight upper bound on the cover time for random walks on graphs
• An Extension of Foster's Network Theorem
• An upper bound on the size of avoidance couplings
• The end time of SIS epidemics driven by random walks on edge-transitive graphs
• TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS
• Random walks on a complete graph: a model for infection
• Collisions of random walks in reversible random graphs
• Sampling random graph homomorphisms and applications to network data analysis
• Meeting times of random walks on graphs
• Exit frequency matrices for finite Markov chains
• Some remarks on cops and drunk robbers
• Some bounds for the Kirchhoff index of graphs
• scientific article; zbMATH DE number 1416163 (Why is no real title available?)
• Monotonicity of avoidance coupling on \(K_N\)
• Exact mixing times for random walks on trees
• Avoidance couplings on non‐complete graphs

This page was built for publication: Collisions Among Random Walks on a Graph

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