P. Berenbrink
Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time
Berenbrink, P.; Cooper, C.; Friedetzky, T.
Abstract
Let G = (V,E) be a connected graph with |V | = n vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an edge-process (or E -process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction. For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the E -process in terms of the edge expansion rate of the graph G, as measured by eigenvalue gap 1 -λmax of the transition matrix of a simple random walk on G. A vertex v is ℓ -good, if any even degree subgraph containing all edges incident with v contains at least ℓ vertices. A graph G is ℓ -good, if every vertex has the ℓ -good property. Let G be an even degree ℓ -good expander of bounded maximum degree. Any E -process on G has vertex cover time equation image This is to be compared with the Ω(nlog n) lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on-line by an adversary. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2013 As no walk based process can cover an n vertex graph in less than n - 1 steps, the cover time of the E -process is of optimal order when ℓ =Θ (log n). With high probability random r -regular graphs, r ≥ 4 even, have ℓ =Ω (log n). Thus the vertex cover time of the E -process on such graphs is Θ(n).
Citation
Berenbrink, P., Cooper, C., & Friedetzky, T. (2015). Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time. Random Structures and Algorithms, 46(1), 36-54. https://doi.org/10.1002/rsa.20504
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 8, 2013 |
Online Publication Date | Jun 27, 2013 |
Publication Date | Jan 1, 2015 |
Deposit Date | Apr 23, 2013 |
Publicly Available Date | Mar 14, 2016 |
Journal | Random Structures and Algorithms |
Print ISSN | 1042-9832 |
Electronic ISSN | 1098-2418 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 46 |
Issue | 1 |
Pages | 36-54 |
DOI | https://doi.org/10.1002/rsa.20504 |
Keywords | Random walk, Cover time, Random graph, Rotor-router model. |
Public URL | https://durham-repository.worktribe.com/output/1478221 |
Related Public URLs | https://arxiv.org/abs/1204.1939 |
Files
Accepted Journal Article
(345 Kb)
PDF
Copyright Statement
This is the accepted version of the following article: Berenbrink, P., Cooper, C. and Friedetzky, T. (2015), Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time. Random Structures & Algorithms, 46(1): 36-54, which has been published in final form at http://dx.doi.org/10.1002/rsa.20504. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
You might also like
Infinite Balanced Allocation via Finite Capacities
(2021)
Presentation / Conference Contribution
Randomized renaming in shared memory systems
(2021)
Journal Article
Time-space trade-offs in population protocols for the majority problem
(2020)
Journal Article
Tight & Simple Load Balancing
(2019)
Presentation / Conference Contribution
A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
(2018)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search