The covertime of a biased random walk on $G_{n,p}$

Colin Cooper, Alan Frieze, Samantha Petti

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…