Collecting coupons on trees, and the cover time of random walks

DOI10.1007/BF01270386zbMath0897.05082MaRDI QIDQ1386177

Uriel Feige

Publication date: 19 October 1998

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

regular graphsspanning treerandom walkhitting timecover timeconjecture of Brightwell and Winkler

Mathematics Subject Classification ID

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

Related Items

Memory Efficient Anonymous Graph Exploration, Hitting Times, Cover Cost, and the Wiener Index of a Tree, On the (reverse) cover cost of trees with some given parameters, The maximum relaxation time of a random walk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random walks and the effective resistance of networks
• Covering problems for Brownian motion on spheres
• The electrical resistance of a graph captures its commute and cover times
• Collisions Among Random Walks on a Graph
• A tight upper bound on the cover time for random walks on graphs
• Extremal cover times for random walks on trees
• A tight lower bound on the cover time for random walks on graphs
• Random Walks on Regular and Irregular Graphs