Covering times of random walks on bounded degree trees and other graphs |
| |
Authors: | David Zuckerman |
| |
Institution: | (1) Division of Computer Science, University of California, 94720 Berkeley, California |
| |
Abstract: | The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)(1) andO(|V| |E|/d
min)(2) imply an upper bound ofO(n
2). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log2
n). The previous lower bound was (|V| log |V|) for trees.(2) In our main result, we show a lower bound of (|V| (log
d
max |V|)2) for trees, which yields a lower bound of (n log2
n). We also extend our techniques to show an upper bound for general graphs ofO(max{E
Ti} log |V|). |
| |
Keywords: | Covering times random walks graphs bounded degree trees balanced binary tree |
本文献已被 SpringerLink 等数据库收录! |
|