Collisions Among Random Walks on a Graph

DOI10.1137/0406029zbMATH Open0776.60083OpenAlexW1964535518MaRDI QIDQ3136609FDOQ3136609

Prasad Tetali, Peter Winkler, Don Coppersmith

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

Recommendations

• Meeting times of random walks on graphs
• scientific article; zbMATH DE number 524141
• scientific article; zbMATH DE number 878897
• Random multiplication approaches uniform measure in finite groups
• Recurrence and collisions of random walks

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)

Cited In (45)

• Collecting coupons on trees, and the cover time of random walks
• Lipschitz embeddings of random sequences
• A tight lower bound on the cover time for random walks on graphs
• Capturing the drunk robber on a graph
• Scheduling of Non-Colliding Random Walks
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• On a Form of Coordinate Percolation
• An Extension of Foster's Network Theorem
• How to meet in anonymous network
• Sampling random graph homomorphisms and applications to network data analysis
• Random walks and flights over connected graphs and complex networks
• Hitting Times, Cover Cost, and the Wiener Index of a Tree
• Some remarks on cops and drunk robbers
• A Hitting Time Formula for the Discrete Green's Function
• Exact computation for meeting times and infection times of random walks on graphs
• Random walks on a complete graph: a model for infection
• Efficient distributed computation of distance sketches in networks
• Avoidance couplings on non‐complete graphs
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• Collisions of random walks in reversible random graphs
• Exact mixing times for random walks on trees
• Exit Frequency Matrices for Finite Markov Chains
• Lipschitz embeddings of random fields
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• The maximum relaxation time of a random walk
• A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents
• 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
• Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time
• The end time of SIS epidemics driven by random walks on edge-transitive graphs
• Collisions of several walkers in recurrent random environments
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Monotonicity of Avoidance Coupling on K_N
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• A tight upper bound on the cover time for random walks on graphs
• An Upper Bound on the Size of Avoidance Couplings
• Improved approximation of the minimum cover time
• Title not available (Why is that?)

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)