|
|||||
|
|
On the cover time of random walks on graphs |
|
| Authors: | Jeff D Kahn Nathan Linial Noam Nisan Michael E Saks |
| Institution: | (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(n
2) 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 等数据库收录！ | |