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

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.

zbMATH Keywords

anonymous graphasynchronous searcherdark cave modelgraph search problempursuit and evasion in graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)