Collisions Among Random Walks on a Graph

DOI10.1137/0406029MaRDI QIDQ3136609zbMATH OpenOpenAlexFDO

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

(51)

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