tailieunhanh - Báo cáo toán học: "The Cover Time of Deterministic Random Walks"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The Cover Time of Deterministic Random Walks. | The Cover Time of Deterministic Random Walks Tobias Friedrich Thomas Sauerwald Max-Planck-Institut fur Informatik Max-Planck-Institut fur Informatik Campus 66123 Saarbrucken Campus 66123 Saarbrucken Germany Germany Submitted Jun 17 2010 Accepted Oct 24 2010 Published Dec 10 2010 Mathematics Subject Classification 05C81 Abstract 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 quickly 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. 1 Introduction We examine the cover time of a simple deterministic process known under various names such as rotor router model or Propp machine. It can be viewed as an attempt to derandomize random walks on graphs G V E . In the model each vertex x G V is equipped with a rotor together with a fixed sequence of the neighbors of x called rotor sequence. While a particle chip coin . performing a random walk leaves a vertex in a random direction the deterministic random walk always goes in the direction the rotor is pointing. After a particle is sent the rotor is updated to the next position of its rotor sequence. We examine how quickly this model covers all vertices and or edges when one particle starts a walk from an arbitrary vertex. An extended abstract 33 of this paper was presented at the 16th Annual International Computing and Combinatorics Conference. This work was done while both authors were postdoctoral fellows at the International Computer .