.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Graph Search Problems with Imperfect Detection
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-06706-7_15.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study graph search problems with imperfect detection. Both graph search and search with imperfect detection are well-studied subjects, but the natural combination is relatively new. In this setting, one is given an edge-weighted graph and a target is hidden at one of the vertices. One can walk through the graph to search for the hidden target and the goal is to find it as soon as possible. However, just visiting a vertex is not sufficient and a search needs to be done which takes a fixed amount of time. Each search attempt is only successful though with probability.., given that the target is at the search location. For the hider, we consider the model where the target is hidden at random, and the adversarial model where the target is placed by an adversary. For the searcher, we consider both pathwise search and expanding search. For all cases, we obtain the first constant factor approximation guarantees.
Keywords:
Approximation algorithms
Graph search
Imperfect detection
Journal
A
IF:
0
Papers:
15
Citations:
0