2026-07-20T05:36:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8909 2024-03-06T10:43:43Z ddc:004 open_access

The Cover Time of a Biased Random Walk on a Random Cubic Graph Cooper, Colin Frieze, Alan Johansson, Tony Random walk random regular graph cover time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Colin Cooper and Alan Frieze and Tony Johansson 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.16 urn:nbn:de:0030-drops-89097 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.16 eng https://creativecommons.org/licenses/by/3.0/legalcode