The Cover Time of Deterministic Random Walks

Details The Cover Time of Deterministic Random Walks The Cover Time of Deterministic Random Walks

2010-06-17

arxiv.org/abs/1006.3430v1

Computer Science

Discrete Mathematics

27 pages, extended version of a conference paper which appeared in the Proceedings of the 16th Annual International Computing

Scientific paper

The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how fast this "deterministic random walk" covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast as the classic random walk. We also examine the short term behavior of deterministic random walks, that is, the time to visit a fixed small number of vertices or edges.

Affiliated with

Also associated with

No associations

Rating

The Cover Time of Deterministic Random Walks 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 The Cover Time of Deterministic Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Cover Time of Deterministic Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-551692