research-article

Tree exploration with logarithmic memory

Authors:

Christoph Ambühl,

Leszek Gąsieniec,

Xiaohui ZhangAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 7, Issue 2

Article No.: 17, Pages 1 - 21

https://doi.org/10.1145/1921659.1921663

Published: 31 March 2011 Publication History

Abstract

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. This strengthens the result from Diks et al. [2004], where O(log ² n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there. We also extend our O(log n)-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however, the explicit values of port numbers are not available.

References

[1]

Albers, S. 1999. Better bounds for online scheduling. SIAM J. Comput. 29, 2, 459--473.

Digital Library

[2]

Aleliunas, R., Karp, R. M., Lipton, R. J., Lovász, L., and Rackoff, C. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS'79). IEEE Computer Society, Los Alamitos, CA, 218--223.

Digital Library

[3]

Alon, N., Azar, Y., and Ravid, Y. 1990. Universal sequences for complete graphs. Discr. Appl. Math. 27, 1-2, 25--28.

Digital Library

[4]

Awerbuch, B., Betke, M., Rivest, R. L., and Singh, M. 1995. Piecemeal graph exploration by a mobile robot (extended abstract). In Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT'95). ACM, New York, 321--328.

Digital Library

[5]

Babai, L., Nisan, N., and Szegedy, M. 1989. Multiparty protocols and logspace-hard pseudorandom sequences (extended abstract). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC'89). ACM, New York, 1--11.

Digital Library

[6]

Bar-Noy, A., Borodin, A., Karchmer, M., Linial, N., and Werman, M. 1989. Bounds on universal sequences. SIAM J. Comput. 18, 2, 268--277.

Digital Library

[7]

Bender, M. A., Fernández, A., Ron, D., Sahai, A., and Vadhan, S. P. 1998. The power of a pebble: Exploring and mapping directed graphs. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98). ACM, New York, 269--278.

Digital Library

[8]

Bender, M. A. and Slonim, D. K. 1994. The power of team exploration: Two robots can learn unlabeled directed graphs. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS'94). IEEE Computer Society, Los Alamitos, CA, 75--85.

Digital Library

[9]

Betke, M., Rivest, R. L., and Singh, M. 1995. Piecemeal learning of an unknown environment. Mach. Learn. 18, 2-3, 231--254.

Digital Library

[10]

Bridgland, M. F. 1987. Universal traversal sequences for paths and cycles. J. Algor. 8, 3, 395--404.

Digital Library

[11]

Buss, J. F. and Tompa, M. 1995. Lower bounds on universal traversal sequences based on chains of length five. Inf. Comput. 120, 2, 326--329.

Digital Library

[12]

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., and Peleg, D. 2008. Label-Guided graph exploration by a finite automaton. ACM Trans. Algor. 4, 4, 1--18.

Digital Library

[13]

Deng, X. and Papadimitriou, C. H. 1999. Exploring an unknown graph. J. Graph Theory 32, 265--297.

Digital Library

[14]

Diks, K., Fraigniaud, P., Kranakis, E., and Pelc, A. 2004. Tree exploration with little memory. J. Algor. 51, 1, 38--63.

Digital Library

[15]

Duncan, C. A., Kobourov, S. G., and Kumar, V. S. A. 2006. Optimal constrained graph exploration. ACM Trans. Algor. 2, 3, 380--402.

Digital Library

[16]

Fraigniaud, P. and Ilcinkas, D. 2004. Digraphs exploration with little memory. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04). Lecture Notes in Computer Science, vol. 2996. Springer, 246--257.

[17]

Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., and Peleg, D. 2005a. Graph exploration by a finite automaton. Theor. Comput. Sci. 345, 2-3, 331--344.

Digital Library

[18]

Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., and Tixeuil, S. 2005b. Space lower bounds for graph exploration via reduced automata. In Proceedings of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO'05). Lecture Notes in Computer Science, vol. 3499. Springer, 140--154.

Digital Library

[19]

Hoory, S. and Wigderson, A. 1993. Universal traversal sequences for expander graphs. Inf. Process. Lett. 46, 2, 67--69.

Digital Library

[20]

Impagliazzo, R., Nisan, N., and Wigderson, A. 1994. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC'94). ACM, New York, 356--364.

Digital Library

[21]

Istrail, S. 1988. Polynomial universal traversing sequences for cycles are constructible (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC'88). ACM, New York, 491--503.

Digital Library

[22]

Karloff, H. J., Paturi, R., and Simon, J. 1988. Universal traversal sequences of length n^o(log n) for cliques. Inf. Process. Lett. 28, 5, 241--243.

Digital Library

[23]

Koucký, M. 2002. Universal traversal sequences with backtracking. J. Comput. Syst. Sci. 65, 4, 717--726.

Digital Library

[24]

Koucký, M. 2003. Log-Space constructible universal traversal sequences for cycles of length o(n^4.03). Theor. Comput. Sci. 296, 1, 117--144.

Digital Library

[25]

Nisan, N. 1992. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449--461.

[26]

Panaite, P. and Pelc, A. 1999. Exploring unknown undirected graphs. J. Algor. 33, 2, 281--295.

Digital Library

[27]

Reingold, O. 2008. Undirected connectivity in log-space. J. ACM 55, 4, 1--24.

Digital Library

Cited By

Das SDereniowski DUznański P(2024)Energy Constrained Depth First SearchAlgorithmica10.1007/s00453-024-01275-8Online publication date: 12-Oct-2024
https://doi.org/10.1007/s00453-024-01275-8
Fekete SNiehs EScheffer CSchmidt A(2022)Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory RobotsAlgorithmica10.1007/s00453-022-00995-z84:10(2954-2986)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00453-022-00995-z
Shimoyama KSudo YKakugawa HMasuzawa T(2022)Invited Paper: One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable CyclesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_2(19-34)Online publication date: 9-Nov-2022
https://doi.org/10.1007/978-3-031-21017-4_2
Show More Cited By

Index Terms

Tree exploration with logarithmic memory
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph enumeration
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching
    2. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Label-guided graph exploration by a finite automaton

A finite automaton, simply referred to as a robot, has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k-state robot, there exists ...
Tree exploration with little memory

A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. While O(...
Tree exploration with logarithmic memory
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 7, Issue 2

March 2011

284 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1921659

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 March 2011

Accepted: 01 April 2009

Revised: 01 December 2008

Received: 01 February 2008

Published in TALG Volume 7, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Royal Society

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
439
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Das SDereniowski DUznański P(2024)Energy Constrained Depth First SearchAlgorithmica10.1007/s00453-024-01275-8Online publication date: 12-Oct-2024
https://doi.org/10.1007/s00453-024-01275-8
Fekete SNiehs EScheffer CSchmidt A(2022)Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory RobotsAlgorithmica10.1007/s00453-022-00995-z84:10(2954-2986)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00453-022-00995-z
Shimoyama KSudo YKakugawa HMasuzawa T(2022)Invited Paper: One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable CyclesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_2(19-34)Online publication date: 9-Nov-2022
https://doi.org/10.1007/978-3-031-21017-4_2
Yakami TYamauchi YKijima SYamashita M(2021)Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchersTheoretical Computer Science10.1016/j.tcs.2021.06.042887:C(11-29)Online publication date: 2-Oct-2021
https://dl.acm.org/doi/10.1016/j.tcs.2021.06.042
Dobrev SKrálovič RPardubská D(2020)Exploration of Time-Varying Connected Graphs with Silent AgentsStructural Information and Communication Complexity10.1007/978-3-030-54921-3_9(146-162)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-54921-3_9
Disser YHackfeld JKlimm M(2019)Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple AgentsJournal of the ACM10.1145/335688366:6(1-41)Online publication date: 16-Oct-2019
https://dl.acm.org/doi/10.1145/3356883
Kshemkalyani AAli FHansdah RKrishnaswamy DVaidya N(2019)Efficient dispersion of mobile robots on graphsProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288610(218-227)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288610
Molla AMoses W(2019)Dispersion of Mobile Robots: The Power of RandomnessTheory and Applications of Models of Computation10.1007/978-3-030-14812-6_30(481-500)Online publication date: 13-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-14812-6_30
Augustine JMoses W(2018)Dispersion of Mobile RobotsProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154293(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154293
Kshemkalyani AAli F(2018)Fast Graph Exploration by a Mobile Robot2018 IEEE First International Conference on Artificial Intelligence and Knowledge Engineering (AIKE)10.1109/AIKE.2018.00025(115-118)Online publication date: Sep-2018
https://doi.org/10.1109/AIKE.2018.00025
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents