|
|||||
|
|
On the cover time of random walks on graphs |
|
| Authors: | Jeff D. Kahn Nathan Linial Noam Nisan Michael E. Saks |
| Affiliation: | (1) Department of Mathematics, Rutgers University, New Brunswick, New Jersey;(2) IBM Almaden, 650 Harry Road, 95120 San Jose, California;(3) Computer Science Department, Hebrew University, Jerusalem, Israel;(4) Computer Science Division, University of California, Berkeley, California;(5) Bell Communications Research, Morristown, New Jersey |
| Abstract: | This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of  (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271. |
| Keywords: | Random walks cover times graphs infinite graphs trees |
| 本文献已被 SpringerLink 等数据库收录！ | |