The Library
New bounds for edge-cover by random walk
Tools
Georgakopoulos, Agelos and Winkler, Peter (2014) New bounds for edge-cover by random walk. Combinatorics, Probability and Computing, Volume 23 (Number 4). pp. 571-584. doi:10.1017/S096354831400008X ISSN 0963-5483.
An open access version can be found in:
Official URL: http://dx.doi.org/10.1017/S096354831400008X
Abstract
We show that the expected time for a random walk on a (multi-)graph G to traverse all m edges of G, and return to its starting point, is at most 2m 2; if each edge must be traversed in both directions, the bound is 3m 2. Both bounds are tight and may be applied to graphs with arbitrary edge lengths. This has interesting implications for Brownian motion on certain metric spaces, including some fractals.
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||||
Publisher: | Cambridge University Press | ||||||||||
ISSN: | 0963-5483 | ||||||||||
Official Date: | July 2014 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 23 | ||||||||||
Number: | Number 4 | ||||||||||
Page Range: | pp. 571-584 | ||||||||||
DOI: | 10.1017/S096354831400008X | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), National Science Foundation (U.S.) (NSF) | ||||||||||
Grant number: | EP/L002787/1 (EPSRC), DMS-0901475 (NSF) | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |