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

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

2012-04-09

arxiv.org/abs/1204.1939v1

Computer Science

Data Structures and Algorithms

12 pages, 1 figure

Scientific 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. We assume there is a rule A, which tells the walk which unvisited edge to use whenever there is a choice. 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. For even degree expander graphs, of bounded maximum degree, we have the following result. Let G be an n vertex even degree expander graph, for which every vertex is in at least one vertex induced cycle of length L. Any edge-process on G has cover time (n+ (n log n)/L). This result is independent of the rule A used to select the order of the unvisited edges, which can be chosen on-line by an adversary. As an example, With high probability, random r-regular graphs, (r at least 4, even), are expanders for which L = Omega(log n). Thus, for almost all such graphs, the vertex cover time of the edge-process is Theta(n). This improves the vertex cover time of such graphs by a factor of log n, compared to the Omega(n log n) cover time of any weighted random walk.

Affiliated with

Also associated with

No associations

Rating

Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652330