Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time

Petra Berenbrink, Colin Cooper, Tom Friedetzky

We consider a modified random walk which uses unvisited edges whenever possible, and makes a simple random walk otherwise. We call such a walk an edge-process. We assume there is a…