article

Tree exploration with little memory

Authors:

Krzysztof Diks,

Pierre Fraigniaud,

Evangelos Kranakis,

Andrzej PelcAuthors Info & Claims

Journal of Algorithms, Volume 51, Issue 1

Pages 38 - 63

https://doi.org/10.1016/j.jalgor.2003.10.002

Published: 01 April 2004 Publication History

Abstract

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(log Δ) bits of memory suffice to explore any tree of maximum degree Δ if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed Ω (log log log n) bits of memory are needed for some such trees of size n). For the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound Ω (log n) on required memory size, and present an algorithm to accomplish this task with O(log² n)-bit memory, for all n-node trees.

References

[1]

{1} S. Albers, M.R. Henzinger, Exploring unknown environments, SIAM J. Comput. 29 (2000) 1164-1188.

Digital Library

[2]

{2} N. Alon, Y. Azar, Y. Ravid, Universal sequences for complete graphs, Discrete Appl. Math. 27 (1990) 25-28.

Digital Library

[3]

{3} B. Awerbuch, M. Betke, R. Rivest, M. Singh, Piecemeal graph learning by a mobile robot, in: Proc. 8th Conf. on Comput. Learning Theory, 1995, pp. 321-328.

[4]

{4} L. Babi, N. Nisan, M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, in: Proc. 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp. 1-11.

[5]

{5} E. Bar-Eli, P. Berman, A. Fiat, R. Yan, On-line navigation in a room, J. Algorithms 17 (1994) 319-341.

Digital Library

[6]

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

Digital Library

[7]

{7} M.A. Bender, A. Fernandez, D. Ron, A. Sahai, S. Vadhan, The power of a pebble: exploring and mapping directed graphs, in: Proc. 30th Annual Symposium on Theory of Computing, 1998, pp. 269-278.

[8]

{8} M.A. Bender, D. Slonim, The power of team exploration: two robots can learn unlabeled directed graphs, in: Proc. 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 75-85.

Digital Library

[9]

{9} A. Blum, P. Raghavan, B. Schieber, Navigating in unfamiliar geometric terrain, SIAM J. Comput. 26 (1997) 110-137.

Digital Library

[10]

{10} M. Betke, R. Rivest, M. Singh, Piecemeal learning of an unknown environment, Machine Learning 18 (1995) 231-254.

Digital Library

[11]

{11} M. Bridgland, Universal traversal sequences for paths and cycles, J. Algorithms 8 (3) (1987) 395-404.

Digital Library

[12]

{12} J. Buss, M. Tompa, Lower bounds on universal traversal sequences based on chains of length five, Inform. and Comput. 120 (2) (1995) 326-329.

Digital Library

[13]

{13} X. Deng, T. Kameda, C.H. Papadimitriou, How to learn an unknown environment, I: The rectilinear case, J. ACM 45 (1998) 215-245.

Digital Library

[14]

{14} X. Deng, C.H. Papadimitriou, Exploring an unknown graph, J. Graph Theory 32 (1999) 265-297.

Digital Library

[15]

{15} C.A. Duncan, S.G. Kobourov, V.S.A. Kumar, Optimal constrained graph exploration, in: Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 807-814.

[16]

{16} S. Hoory, A. Widgerson, Universal traversal sequences for expander graphs, Inform. Process. Lett. 46 (2) (1993) 67-69.

Digital Library

[17]

{17} R. Impagliazza, N. Nisan, A. Widgerson, Pseudorandomness for network algorithms, in: Proc. 26th Annual ACM Symposium on Theory of Computing (STOC), 1994, pp. 356-364.

[18]

{18} S. Istrail, Polynomial universal traversing sequences for cycles are constructible, in: Proc. 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 491-503.

[19]

{19} H. Karloff, R. Paturi, J. Simon, Universal traversal sequences of length nlogn for cliques, Inform. Process. Lett. 28 (5) (1988) 241-243.

Digital Library

[20]

{20} M. Koucky, Log-space constructible universal traversal sequences for cycles of length O(n4.03), in: Proc. Electronic Colloquium on Computational Complexity, Report TR01-13, 2001, http://www.eccc.unitrier.de/eccc.

[21]

{21} M. Koucky, Universal traversal sequences with backtracking, in: Proc. 16th IEEE Conference on Computational Complexity, 2001, pp. 21-26; J. Comput. System Sci., submitted for publication.

[22]

{22} N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica 12 (4) (1992) 449-461.

[23]

{23} P. Panaite, A. Pelc, Exploring unknown undirected graphs, J. Algorithms 33 (1999) 281-295.

Digital Library

[24]

{24} N.S.V. Rao, S. Hareti, W. Shi, S.S. Iyengar, Robot navigation in unknown terrains: introductory survey of non-heuristic algorithms. Tech. Report ORNL/TM-12410, Oak Ridge National Laboratory, July 1993.

Cited By

Das SDhar AGorain BMahawar M(2025)Collision-free Exploration by Mobile Agents Using PebblesProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700863(161-170)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700863
Pattanayak DPelc A(2024)Graph exploration by a deterministic memoryless automaton with pebblesDiscrete Applied Mathematics10.1016/j.dam.2024.05.024356:C(149-160)Online publication date: 30-Oct-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.05.024
Böckenhauer HFuchs JUnger W(2023)Exploring sparse graphs with adviceInformation and Computation10.1016/j.ic.2022.104950289:PAOnline publication date: 20-Jan-2023
https://dl.acm.org/doi/10.1016/j.ic.2022.104950
Show More Cited By

Index Terms

Tree exploration with little memory

Recommendations

Tree exploration with little memory
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

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

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 ...
Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents

We study the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 51, Issue 1

1 April 2004

104 pages

ISSN:0196-6774

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Das SDhar AGorain BMahawar M(2025)Collision-free Exploration by Mobile Agents Using PebblesProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700863(161-170)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700863
Pattanayak DPelc A(2024)Graph exploration by a deterministic memoryless automaton with pebblesDiscrete Applied Mathematics10.1016/j.dam.2024.05.024356:C(149-160)Online publication date: 30-Oct-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.05.024
Böckenhauer HFuchs JUnger W(2023)Exploring sparse graphs with adviceInformation and Computation10.1016/j.ic.2022.104950289:PAOnline publication date: 20-Jan-2023
https://dl.acm.org/doi/10.1016/j.ic.2022.104950
Das ABose KSau B(2023)Memory optimal dispersion by anonymous mobile robotsDiscrete Applied Mathematics10.1016/j.dam.2023.07.005340:C(171-182)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.07.005
Borst SDadush DHuiberts SKashaev D(2023)A Nearly Optimal Randomized Algorithm for Explorable Heap SelectionInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_3(29-43)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32726-1_3
Gorain BPatra SSingh R(2023)Graph Covering Using Bounded Size SubgraphsAlgorithms and Discrete Applied Mathematics10.1007/978-3-031-25211-2_32(415-426)Online publication date: 9-Feb-2023
https://dl.acm.org/doi/10.1007/978-3-031-25211-2_32
Dhar AGorain BMondal KPatra SSingh R(2022)Edge exploration of anonymous graph by mobile agent with external helpComputing10.1007/s00607-022-01136-8105:2(483-506)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1007/s00607-022-01136-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: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_2
Czyzowicz JDereniowski DPelc A(2021)Building a Nest by an AutomatonAlgorithmica10.1007/s00453-020-00752-083:1(144-176)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s00453-020-00752-0
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents