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

DOI10.1016/J.TCS.2021.06.042OpenAlexW3177877466MaRDI QIDQ820530FDOQ820530

Authors Takahiro Yakami, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita 

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

anonymous graphasynchronous searcherdark cave modelgraph search problempursuit and evasion in graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Searching for an evader in an unknown graph by an optimal number of searchers
• On-line search in two-dimensional environment
• On-line search in two-dimensional environment
• Distributed graph searching with a sense of direction
• On certain search problems with counteraction.

Cites work

• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 1754612 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 1445396 (Why is no real title available?)
• Algorithms – ESA 2004
• An alternative proof for the equivalence of searcher and 2-searcher
• An annotated bibliography on guaranteed graph searching
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Decontamination of hypercubes by mobile agents
• Distributed Chasing of Network Intruders
• Graph minors. XIII: The disjoint paths problem
• Interval graphs and searching
• Monotonicity in graph searching
• Nonconstructive tools for proving polynomial-time decidability
• Recontamination does not help to search a graph
• Searching and pebbling
• Searching for a Mobile Intruder in a Polygonal Region
• Searching for mobile intruders in a polygonal region by a group of mobile searchers
• The complexity of searching a graph
• The cost of monotonicity in distributed graph searching
• Tree exploration with logarithmic memory
• Undirected connectivity in log-space
• Universal traversal sequences with backtracking.

Cited in

(2)

• Searching for an evader in an unknown graph by an optimal number of searchers
• Multiple searchers searching for a randomly distributed immobile target on a unit network

This page was built for publication: Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820530)