Random walks which prefer unvisited edges.
Petra Berenbrink, Colin Cooper, Tom Friedetzky · 2012
In this paper, 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 (or E-process). We assume there is a rule A, which tells the walk which unvisited edge to use whenever there are several unvisited edges. In the simplest case, A is a uniform random choice over unvisited edges incident with the current walk position. However we do not exclude arbitrary choices of rule A. For example, the rule could be determined on-line by an adversary, or could vary from vertex to vertex.