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

DOI10.1016/j.tcs.2021.06.042OpenAlexW3177877466MaRDI QIDQ820530

Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Takahiro Yakami

Publication date: 27 September 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.06.042

zbMATH Keywords

graph search problemanonymous graphasynchronous searcherdark cave modelpursuit and evasion in graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An alternative proof for the equivalence of searcher and 2-searcher
• An annotated bibliography on guaranteed graph searching
• Interval graphs and searching
• Searching and pebbling
• Universal traversal sequences with backtracking.
• Graph minors. XIII: The disjoint paths problem
• The cost of monotonicity in distributed graph searching
• Decontamination of hypercubes by mobile agents
• Tree exploration with logarithmic memory
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Undirected connectivity in log-space
• Distributed Chasing of Network Intruders
• The complexity of searching a graph
• Nonconstructive tools for proving polynomial-time decidability
• Monotonicity in graph searching
• Searching for a Mobile Intruder in a Polygonal Region
• How to meet asynchronously at polynomial cost
• Recontamination does not help to search a graph
• Algorithms – ESA 2004
• Searching for mobile intruders in a polygonal region by a group of mobile searchers