Abstract
We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled i, the robot proceeds with its exploration, leaving via the edge having label [i mod deg (v)]+1 at v.
A lot of attention has been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length π. It has recently been proved (Czyzowicz et al., Proc. SIROCCO’09, 2009) that \(\pi\leq4\frac{1}{3}n\) holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π≤4n−2. This main result is shown to be tight with respect to the class of labellings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Budach, L.: Automata and labyrinths. Math. Nachr. 86, 195–282 (1978)
Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 1–18 (2008)
Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. Algorithmica 53(1), 1–15 (2009)
Cook, S., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM J. Comput. 9(3), 636–652 (1980)
Czyzowicz, J., Dobrev, S., Gąsieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, Y., Martin, R.A., Sadakane, K., Sung, W.K.: More efficient periodic traversal in anonymous undirected graphs. In: Proceedings of the 16th Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 5869, pp. 167–181 (2009)
Dobrev, S., Jansson, J., Sadakane, K., Sung, W.K.: Finding short right-hand-on-the-wall walks in graphs. In: Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 3499, pp. 127–139 (2005)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2–3), 331–344 (2005)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Impact of memory size on graph exploration capability. Discrete Appl. Math. 156(12), 2310–2319 (2008)
Gąsieniec, L., Klasing, R., Martin, R.A., Navarra, A., Zhang, X.: Fast periodic graph exploration with constant memory. J. Comput. Syst. Sci. 74(5), 802–822 (2008)
Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). LNCS, vol. 5344, pp. 14–29 (2008)
Ilcinkas, D.: Setting port numbers for fast graph exploration. Theor. Comput. Sci. 401(1–3), 236–242 (2008)
Kosowski, A., Navarra, A.: Graph decomposition for improving memoryless periodic exploration. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS). LNCS, vol. 5734, pp. 501–512 (2009)
Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 376–385 (2005)
Rollik, H.: Automaten in planaren graphen. Acta Inform. 13, 287–298 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research was partially funded by the State Committee for Scientific Research (Poland) Grant 4 T11C 047 25, by the ANR-project “ALADDIN” (France), and by the project “CEPAGE” of INRIA (France).
An extended abstract of this paper appeared in the proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS) [12].
Rights and permissions
About this article
Cite this article
Kosowski, A., Navarra, A. Graph Decomposition for Memoryless Periodic Exploration. Algorithmica 63, 26–38 (2012). https://doi.org/10.1007/s00453-011-9518-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9518-1