A TIGHT LOWER-BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS

Authors
FEIGE U
Citation
U. Feige, A TIGHT LOWER-BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS, Random structures & algorithms, 6(4), 1995, pp. 433-438
Citations number
17
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
6
Issue
4
Year of publication
1995
Pages
433 - 438
Database
ISI
SICI code
1042-9832(1995)6:4<433:ATLOTC>2.0.ZU;2-G
Abstract
We prove that the expected time for a random walk to cover all n verti ces of a graph is at least (1 + o(1))n ln n. (C) 1995 John Wiley & Son s, Inc.