Improved approximation of the minimum cover time

DOI10.1016/j.tcs.2005.03.042zbMath1077.68068OpenAlexW1970421460MaRDI QIDQ2566000

Eden Chlamtáč, Uriel Feige

Publication date: 22 September 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.042

zbMATH Keywords

Markov chainsApproximation algorithmsRandom walksCover time

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Covering problems for Markov chains
• Random walks and the effective resistance of networks
• Collisions Among Random Walks on a Graph
• Design of On-Line Algorithms Using Hitting Times
• An Extension of Foster's Network Theorem
• Deterministic approximation of the cover time

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