The cover time of a biased random walk on G_n,p

DOI10.1137/1.9781611975062.14MaRDI QIDQ5195115zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Samantha Petti, Alan Frieze

Publication date 18 September 2019

Published in 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04908

zbMATH Keywords

lollipop graphvertex cover time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Abstract: We analyze the covertime of a biased random walk on the random graph $G_{n,p}$. The walk is biased towards visiting vertices of low degree and this makes the covertime less than in the unbiased case

Recommendations

• The cover time of a biased random walk on a random cubic graph
• The cover time of a biased random walk on a random regular graph of odd degree
• The cover time of a biased random walk on a random regular graph of odd degree
• Random walks with the minimum degree local rule have O(N^2) cover time
• Random walks with the minimum degree local rule have O(n^2) cover time

Cited in

(7)

• Biased random walks
• The cover time of a biased random walk on a random regular graph of odd degree
• Comparison of mean hitting times for a degree-biased random walk
• Random walks with the minimum degree local rule have O(n^2) cover time
• Random walks with the minimum degree local rule have O(N^2) cover time
• The cover time of a biased random walk on a random cubic graph
• The cover time of a biased random walk on a random regular graph of odd degree

This page was built for publication: The cover time of a biased random walk on \(G_{n,p}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5195115)