Abstract
R. Borie, S. Koenig and C. Tovey. Section 9.5: Pursuit-Evasion Problems. In Handbook of Graph Theory, J. Gross, J. Yellen and P. Zhang (editor), 1145-1165. Chapman and Hall/CRC, 2013.Abstract: In pursuit-evasion problems, a team of mobile pursuers (or searchers) attempts to capture one or more mobile evaders (fugitives, intruders) within a graph. For example, the pursuers may represent soldiers, policemen, or robots. The evaders might be terrorists, criminals, lost children, or even a poisonous gas. The graph may represent a road map, building floor plan, cave system, pipe network, etc. Many distinct variations of pursuit-evasion problems can be formulated by specifying the rules of movement for the pursuers and for the evaders, the knowledge each opponent has about the other, the rules of capture, the kind of graph, and the objective function. Typical objectives include minimizing the number of pursuers, the distance traveled by pursuers, or the elapsed time until capture. Because finiteness of the latter two objectives is equivalent to optimization of the first objective, the complexity of the latter two problems is bounded below by that of the first. However, optimization of the first objective is usually NP-hard for general graphs, hence the bulk of the graph-theoretic pursuit-evasion literature focuses on that objective. The following subsections discuss several of the most-studied pursuit-evasion variations.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.