Document Open Access Logo

The Cover Time of a Biased Random Walk on a Random Cubic Graph

Authors Colin Cooper, Alan Frieze, Tony Johansson

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.16.pdf
  • Filesize: 474 kB
  • 12 pages

Document Identifiers

Author Details

Colin Cooper
  • Department of Informatics, King’s College, University of London, London WC2R 2LS, UK
Alan Frieze
  • Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA
Tony Johansson
  • Department of Mathematics, Uppsala University, 751 05 Uppsala, Sweden

Funding

  • Cooper, Colin: Research supported in part by EPSRC grants EP/J006300/1 and EP/M005038/1.
  • Frieze, Alan: Research supported in part by NSF grant DMS0753472.
  • Johansson, Tony: Research supported in part by the Knut and Alice Wallenberg Foundation.

Cite As Get BibTex

Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.16

Abstract

We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Random walk
  • random regular graph
  • cover time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 132-140. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28410.
  2. David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  3. Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 09(04):585-603, 2007. URL: http://dx.doi.org/10.1142/S0219199707002551.
  4. Petra Berenbrink, Colin Cooper, and Tom Friedetzky. Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time. Random Struct. Algorithms, 46(1):36-54, 2015. URL: http://dx.doi.org/10.1002/rsa.20504.
  5. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb., 1(4):311-316, 1980. URL: http://dx.doi.org/10.1016/S0195-6698(80)80030-8.
  6. Colin Cooper and Alan M. Frieze. The cover time of random regular graphs. SIAM J. Discrete Math., 18(4):728-740, 2005. URL: http://dx.doi.org/10.1137/S0895480103428478.
  7. Colin Cooper and Alan M. Frieze. Vacant sets and vacant nets: Component structures induced by a random walk. SIAM J. Discrete Math., 30(1):166-205, 2016. URL: http://dx.doi.org/10.1137/14097937X.
  8. Colin Cooper, Alan M. Frieze, and Samantha Petti. The cover time of a biased random walk on G_n, p. In Markus E. Nebel and Stephan G. Wagner, editors, Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018, New Orleans, LA, USA, January 8-9, 2018., pages 158-167. SIAM, 2018. URL: http://dx.doi.org/10.1137/1.9781611975062.14.
  9. Uriel Feige. A tight lower bound on the cover time for random walks on graphs. Random Struct. Algorithms, 6(4):433-438, 1995. URL: http://dx.doi.org/10.1002/rsa.3240060406.
  10. Uriel Feige. A tight upper bound on the cover time for random walks on graphs. Random Struct. Algorithms, 6(1):51-54, 1995. URL: http://dx.doi.org/10.1002/rsa.3240060106.
  11. Joel Friedman. A proof of Alon’s second eigenvalue conjecture. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 720-724, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780646.
  12. Alan M. Frieze and Michal Karonski. Introduction to Random Graphs. Cambridge University Press, Cambridge, UK, 2015. URL: http://dx.doi.org/10.1017/CBO9781316339831.011.
  13. Tal Orenshtein and Igor Shinkar. Greedy random walk. Combinatorics, Probability & Computing, 23(2):269-289, 2014. URL: http://dx.doi.org/10.1017/S0963548313000552.
  14. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput., 82(1):93-133, 1989. URL: http://dx.doi.org/10.1016/0890-5401(89)90067-9.
  15. Hui Tian, Hong Shen, and Teruo Matsuzawa. RandomWalk routing for wireless sensor networks. In Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2005), 5-8 December 2005, Dalian, China, pages 196-200. IEEE Computer Society, 2005. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=10544, URL: http://dx.doi.org/10.1109/PDCAT.2005.193.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact