Abstract
R. Borie, C. Tovey, K. Daniel and S. Koenig. ESP: Pursuit Evasion on Series-Parallel Graphs. Technical Report Department of Computer Science, University of Southern California, Los Angeles (California), 2009.Abstract: We study pursuit-evasion problems where pursuers have to clear a given graph of fast-moving evaders despite poor visibility, for example, where police search a cave system to ensure that no terrorists are hiding in it. If the vertex connectivity of some part of the graph exceeds the number of pursuers, the evaders can always avoid capture. We therefore focus on graphs whose subgraphs can always be cut at a limited number of vertices, that is, graphs of low treewidth. However, solving pursuit-evasion problems optimally is NP-hard even for the simplest of these graph classes. In this paper, we therefore develop a heuristic approach, called ESP, that solves large pursuit-evasion problems on series-parallel (that is, treewidth-two) graphs quickly and with small costs. It exploits their topology by performing dynamic programming on their decomposition graphs. We apply ESP to different kinds of series-parallel graphs and show that it scales up to larger graphs than a strawman approach based on previous results from the literature.
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.