DocumentCode :
2735016
Title :
The cover time, the blanket time, and the Matthews bound
Author :
Kahn, J. ; Kim, J.H. ; Lovász, L. ; Vu, V.H.
Author_Institution :
Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
fYear :
2000
fDate :
2000
Firstpage :
467
Lastpage :
475
Abstract :
We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M/2<C= O(M(lnlnn)2 ). We give a deterministic-polynomial time algorithm to approximate M within a factor of 2; this then approximates C within a factor of O((lnlnn)2), improving the previous bound O(lnn) due to Matthews. The blanket time B was introduced by P. Winkler and D. Zuckerman (1996): it is the expectation of the first time when all vertices are visited within a constant factor of the number of times suggested by the stationary distribution. Obviously C⩽B. Winkler and Zuckerman conjectured B=O(C) and proved B=O(Clnn). Our bounds above are also valid for the blanket time, and so it follows that B=O(C(lnlnn)2)
Keywords :
approximation theory; computational complexity; deterministic algorithms; graph theory; theorem proving; Matthews bound; Matthews bounds; approximation algorithm; blanket time; cover time; deterministic-polynomial time algorithm; graph; random walk; stationary distribution; Approximation algorithms; Mathematics; Polynomials; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on
Conference_Location :
Redondo Beach, CA
ISSN :
0272-5428
Print_ISBN :
0-7695-0850-2
Type :
conf
DOI :
10.1109/SFCS.2000.892134
Filename :
892134
Link To Document :
بازگشت