For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2015/10/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
graph exploration, mobile agent, whiteboard,
Full Text: PDF(1.9MB)>>
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].