The cover time, the blanket time, and the Matthews bound
J. Kahn, J.H. Kim, László Lovász, Van H. Vu · 2002
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