TY - GEN
T1 - Tree exploration with logarithmic memory
AU - Gąsieniec, Leszek
AU - Pelc, Andrzej
AU - Radzik, Tomasz
AU - Zhang, Xiaohui
N1 - Funding Information:
Research partly supported by NSERC discovery grant, and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.
PY - 2007
Y1 - 2007
N2 - 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(log2 n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there.
AB - 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(log2 n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there.
UR - http://www.scopus.com/inward/record.url?scp=84969247968&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969247968&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84969247968
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 585
EP - 594
BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PB - Association for Computing Machinery
T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Y2 - 7 January 2007 through 9 January 2007
ER -