Deterministic approximation of the cover time

DOI10.1002/RSA.10083MaRDI QIDQ4417001zbMATH OpenOpenAlexFDO

Authors Yuri Rabinovich, Uriel Feige

Publication date 6 August 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.10083

zbMATH Keywords

random walk

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Improved approximation of the minimum cover time
• The evolution of the cover time
• On the cover time of random walks on graphs
• Bounds on the cover time
• Lower bounds for covering times for reversible Markov chains and random walks on graphs

Cited in

(7)

• Bounds on the cover time
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• Improved approximation of the minimum cover time
• Cover times, blanket times, and majorizing measures
• Cover times, blanket times, and majorizing measures
• On the \(\alpha\)-lazy version of Markov chains in estimation and testing problems
• On approximate majority and probabilistic time

This page was built for publication: Deterministic approximation of the cover time

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