A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards

• SUDO Yuichi

  NTT Secure Platform Laboratories, NTT Corporation Graduate School of Information Science and Technology, Osaka University

• BABA Daisuke

  TIS Inc.

• NAKAMURA Junya

  Information and Media Center, Toyohashi University of Technology

• OOSHITA Fukuhito

  Graduate School of Information Science and Technology, Osaka University

• KAKUGAWA Hirotsugu

  Graduate School of Information Science and Technology, Osaka University

• MASUZAWA Toshimitsu

  Graduate School of Information Science and Technology, Osaka University

Abstract

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

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (10), 2117-2128, 2015

  The Institute of Electronics, Information and Communication Engineers

Keywords

• graph exploration
• mobile agent
• whiteboard

Details

• CRID: 1390282681286710912
• NII Article ID: 120005895730
• NII Article ID: 130005100673
• DOI: 10.1587/transfun.e98.a.2117
• ISSN: 17451337
• ISSN: 09168508
• HANDLE: 10061/11101
• Web Site: https://naist.repo.nii.ac.jp/records/3936
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E98.A/10/E98.A_2117/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed