A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards

Yuichi SUDO  Daisuke BABA  Junya NAKAMURA  Fukuhito OOSHITA  Hirotsugu KAKUGAWA  Toshimitsu MASUZAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.10   pp.2117-2128
Publication Date: 2015/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.2117
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
graph exploration,  mobile agent,  whiteboard,  

Full Text: PDF(1.9MB)>>
Buy this Article

We consider the exploration problem with a single agent in an undirected graph. The problem requires the agent starting from an arbitrary node to explore all the nodes and edges in the graph and return to the starting node. Our goal is to minimize both the number of agent moves and the memory size of the agent, which dominate the amount of communication during the exploration. We focus on the local memory called the whiteboard of each node. There are several exploration algorithms which are very fast (i.e. the exploration is completed within a small number of agent moves such as 2m and m+3n) and do not use whiteboards. These algorithms, however, require large agent memory because the agent must keep the entire information in its memory to explore a graph. We achieve the above goal by reducing the agent memory size of such algorithms with using whiteboards. Specifically, we present two algorithms with no agent memory based on the traditional depth-first traversal and two algorithms with O(n) and O(nlog n) space of agent memory respectively based on the fastest algorithms in the literature by Panaite and Pelc [J. Alg., Vol.33 No.2, 1999].