Linear cover time is exponentially unlikely
成果类型：
Article
署名作者：
Benjamini, Itai; Gurel-Gurevich, Ori; Morris, Ben
署名单位：
Weizmann Institute of Science; University of British Columbia; University of California System; University of California Davis
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-011-0403-2
发表日期：
2013
页码：
451-461
关键词：
摘要：
We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. We conjecture that the same holds for any simple graph.