Abstract
The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G = (V,E), where |V| = n and |E| = m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In recent work [11] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2mD, where D is the diameter of G.
In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player \(\cal P\) intending to lock-in the agent in an Euler tour as quickly as possible and its adversary \(\cal A\) with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time O(m). On the other hand we show that if adversary \(\cal A\) is solely responsible for the assignment of ports and pointers, the lock-in time Ω(m·D) can be enforced in any graph with m edges and diameter D. Furthermore, we show that if \(\cal A\) provides its own port numbering after the initial setup of pointers by \(\cal P\), the complexity of the lock-in problem is bounded by O(m · min {logm,D}). We also propose a class of graphs in which the lock-in requires time Ω(m ·logm). In the remaining two cases we show that the lock-in requires time Ω(m ·D) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is O(m).
This work was done during the visit of the second author in Bordeaux.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs (2001), http://stat-www.berkeley.edu/users/aldous/RWG/book.html
Afek, Y., Gafni, E.: Distributed Algorithms for Unidirectional Networks. SIAM Journal on Computing 23(6), 1152–1178 (1994)
Bhatt, S., Even, S., Greenberg, D., Tayar, R.: Traversing Directed Eulerian Mazes. Journal of Graph Algorithms and Applications 6(2), 157–173 (2002)
Cooper, C., Ilcinkas, D., Klasing, R., Kosowski, A.: Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Niko-letsea, S. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 411–422. Springer, Heidelberg (2009)
Cooper, J.N., Spencer, J.: Simulating a random walk with constant error. Combinatorics, Probability and Computing 15, 815–822 (2006)
Doerr, B., Friedrich, T.: Deterministic Random Walks on the Two-Dimensional Grid. Combinatorics, Probability and Computing 18(1-2), 123–144 (2009)
Fraenkel, A.S.: Economic traversal of labyrinths. Mathematics Magazine 43, 125–130 (1970)
Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14–29. Springer, Heidelberg (2008)
Priezzhev, V.B., Dhar, D., Dhar, A., Krishnamurthy, S.: Eulerian walkers as a model of selforganized criticality. Physics Review Letters 77, 5079–5082 (1996)
Strahler, A.N.: Hypsometric (area-altitude) analysis of erosional topography. Geological Society of America Bulletin 63(11), 1117–1142 (1952)
Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A Distributed Ant Algorithm for Efficiently Patrolling a Network. Algorithmica 37, 165–186 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bampas, E., Gąsieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A. (2009). Euler Tour Lock-In Problem in the Rotor-Router Model. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)