Covering times of random walks on bounded degree trees and other graphs

DOI10.1007/BF01048276MaRDI QIDQ582702zbMATH OpenFDO

Authors David Zuckerman

Publication date 1989

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01048276

zbMATH Keywords

covering timesrandom walktrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stopping times; optimal stopping problems; gambling theory (60G40) Sums of independent random variables; random walks (60G50)

Review text

Upper and lower bounds are given for the expected length of a random walk that is performed on a tree until it is covered.

Cites work

• Finite Continuous Time Markov Chains
• scientific article; zbMATH DE number 3936137 (Why is no real title available?)
• Markov chain models - rarity and exponentiality
• On the cover time of random walks on graphs
• Random walks on random trees

Cited in

(8)

• A bound for the covering time of random walks on graphs
• Covering with blocks in the non-symmetric case
• Threshold limits for cover times
• A Spanning Tree Method for Bounding Hitting Times of Random Walks on Graphs
• Cover time for branching random walks on regular trees
• Many Random Walks Are Faster Than One
• New bounds for edge-cover by random walk
• Random walk covering of some special trees

This page was built for publication: Covering times of random walks on bounded degree trees and other graphs

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