Article

Tree exploration with logarithmic memory

Authors:

Leszek Gasieniec,

Xiaohui ZhangAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 585 - 594

Published: 07 January 2007 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 [15], where O(log² n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there.

References

[1]

S. Albers and M. R. Henzinger, Exploring unknown environments, SIAM Journal on Computing 29 (2000), 1164--1188.

Digital Library

[2]

R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász and C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. 20th Ann. Symp. on Foundations of Computer Science (FOCS 1979), 218--223.

[3]

N. Alon, Y. Azar, and Y. Ravid, Universal sequences for complete graphs, Discrete Applied Mathematics 27 (1990), 25--28.

Digital Library

[4]

B. Awerbuch, M. Betke, R. Rivest and M. Singh, Piecemeal graph learning by a mobile robot, Proc. 8th Conf. on Comput. Learning Theory (1995), 321--328.

Digital Library

[5]

L. Babi, N. Nisan, and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, Proc 21st Ann. ACM Symposium on Theory of Computing (STOC 1989), 1--11.

Digital Library

[6]

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

Digital Library

[7]

M. A. Bender, A. Fernandez, D. Ron, A. Sahai and S. Vadhan, The power of a pebble: Exploring and mapping directed graphs, Proc. 30th Ann. Symp. on Theory of Computing (STOC 1998), 269--278.

Digital Library

[8]

M. A. Bender and D. Slonim, The power of team exploration: Two robots can learn unlabeled directed graphs, Proc. 35th Ann. Symp. on Foundations of Computer Science (FOCS 1994), 75--85.

[9]

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

Digital Library

[10]

M. Bridgland, Universal traversal sequences for paths and cycles, Journal of Algorithms 8 (1987), 395--404.

Digital Library

[11]

J. Buss, and M. Tompa, Lower bounds on universal traversal sequences based on chains of length five, Information and Computation 120 (1995), 326--329.

Digital Library

[12]

R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, D. Peleg, Label-guided graph exploration by a finite automaton, Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), LNCS 3580, 335--346.

Digital Library

[13]

X. Deng, T. Kameda and C. H. Papadimitriou, How to learn an unknown environment I: the rectilinear case, Journal of the ACM 45 (1998), 215--245.

Digital Library

[14]

X. Deng and C. H. Papadimitriou, Exploring an unknown graph, Journal of Graph Theory 32 (1999), 265--297.

Digital Library

[15]

K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc, Tree exploration with little memory, Journal of Algorithms 51 (2004), 38--63.

Digital Library

[16]

C. A. Duncan, S. G. Kobourov and V. S. A. Kumar, Optimal constrained graph exploration, Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (2001), 807--814.

Digital Library

[17]

P. Fraigniaud, D. Ilcinkas, Digraphs exploration with little memory, Proc. 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS 2004), LNCS 2996, 246--257.

[18]

P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, D. Peleg, Graph exploration by a finite automaton, Theoretical Computer Science 345 (2005), 331--344.

Digital Library

[19]

P. Fraigniaud, D. Ilcinkas, S. Rajsbaum, S. Tixeuil, Space lower bounds for graph exploration via reduced automata, Proc. 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), LNCS 3499, 140--154.

Digital Library

[20]

S. Hoory, and A. Widgerson, Universal traversal sequences for expander graphs, Information Processing Letters, 46 (1993), 67--69.

Digital Library

[21]

R. Impagliazza, N. Nisan, A. Widgerson, Pseudorandomness for network algorithms, Proc 26th Ann. ACM Symposium on Theory of Computing (STOC 1994), 356--364.

Digital Library

[22]

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

Digital Library

[23]

H. Karloff, R. Paturi and J. Simon, Universal traversal sequences of length n ^{log n} for cliques, Information Processing Letters, 28 (1988), 241--243.

Digital Library

[24]

M. Koucky, Log-space constructible universal traversal sequences for cycles of length O(n ^4.03), Proc. Electronic Colloquium on Computational Complexity, Report TR01--13, http://www.eccc.uni-trier.de/eccc, 2001.

[25]

M. Koucky, Universal Traversal Sequences with Backtracking, Proc. 16th IEEE Conference on Computational Complexity (2001), 21--26.

Digital Library

[26]

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

[27]

P. Panaite and A. Pelc, Exploring unknown undirected graphs, Journal of Algorithms 33 (1999), 281--295.

Digital Library

[28]

O. Reingold, Undirected ST-connectivity in log-space, Proc 37th Annual ACM Symposium on Theory of Computing (STOC 1998), 376--385.

Digital Library

Cited By

Lenzen CLynch NNewport CRadeva THalldórsson MDolev S(2014)Trade-offs between selection complexity and performance when searching the plane without communicationProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611463(252-261)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611463
Fraigniaud PPelc A(2013)Delays Induce an Exponential Memory Gap for Rendezvous in TreesACM Transactions on Algorithms (TALG)10.1145/2438645.24386499:2(1-24)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438649
Feinerman OKorman ALotker ZSereni JKowalski DPanconesi A(2012)Collaborative search on the plane without communicationProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332444(77-86)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332444
Show More Cited By

Tree exploration with logarithmic memory
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

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 ...
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 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(...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
283
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lenzen CLynch NNewport CRadeva THalldórsson MDolev S(2014)Trade-offs between selection complexity and performance when searching the plane without communicationProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611463(252-261)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611463
Fraigniaud PPelc A(2013)Delays Induce an Exponential Memory Gap for Rendezvous in TreesACM Transactions on Algorithms (TALG)10.1145/2438645.24386499:2(1-24)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438649
Feinerman OKorman ALotker ZSereni JKowalski DPanconesi A(2012)Collaborative search on the plane without communicationProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332444(77-86)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332444
Feinerman OKorman A(2012)Memory lower bounds for randomized collaborative search and implications for biologyProceedings of the 26th international conference on Distributed Computing10.1007/978-3-642-33651-5_5(61-75)Online publication date: 16-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33651-5_5
Dieudonné YPelc A(2012)Deterministic network exploration by anonymous silent agents with local traffic reportsProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_45(500-512)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_45
Dereniowski DPelc A(2010)Drawing maps with adviceProceedings of the 24th international conference on Distributed computing10.5555/1888781.1888821(328-342)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888781.1888821
Friedrich TSauerwald T(2010)The cover time of deterministic random walksProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886831(130-139)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886831
Sudo YBaba DNakamura JOoshita FKakugawa HMasuzawa TPetit FTixeuil S(2010)An agent exploration in unknown undirected graphs with whiteboardsProceedings of the Third International Workshop on Reliability, Availability, and Security10.1145/1953563.1953570(1-6)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1953563.1953570
Czyzowicz JKosowski APelc ARicha AGuerraoui R(2010)How to meet when you forgetProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835801(450-459)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835801
Fraigniaud PPelc Aauf der Heide FPhillips C(2010)Delays induce an exponential memory gap for rendezvous in treesProceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures10.1145/1810479.1810524(224-232)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810479.1810524
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten