Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers

Takahiro Yakami, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review


The graph search problem is the problem of searching for a mobile evader in a dark cave by a group of mobile searchers, where the cave is modeled by an undirected connected graph G. An offline and centralized version of the graph search problem is formalized as a pebble game on G, and has been extensively investigated under the name of the edge search problem. By es(G) we denote the number of pebbles (i.e., searchers) necessary and sufficient to edge search G. An online and distributed version of the graph search problem is the graph search by mobile agents. We investigate the graph search problem under a weaker online and distributed setting called the dark cave model, which models the dark cave more directly than a graph; G is completely anonymous, and we do not introduce any artificial facilities in G such as a port numbering, a homebase, and a whiteboard. Instead, we assume that the searchers can exchange information wherever they meet. Under the dark cave model, we propose a search algorithm OLSEARCH for es(G) searchers, and show that it is optimal in terms of the number of searchers.

Original languageEnglish
Pages (from-to)11-29
Number of pages19
JournalTheoretical Computer Science
Publication statusPublished - Oct 2 2021

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers'. Together they form a unique fingerprint.

Cite this