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

Authors
FEIGE U
Citation
U. Feige, A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS, Random structures & algorithms, 6(1), 1995, pp. 51-54
Citations number
8
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
6
Issue
1
Year of publication
1995
Pages
51 - 54
Database
ISI
SICI code
1042-9832(1995)6:1<51:ATUBOT>2.0.ZU;2-E
Abstract
We prove that the expected time for a random walk to visit all n verti ces of a connected graph is at most 4/27 n3 + o(n3). (C) 1995 John Wil ey & Sons, Inc.