Access Restriction

Author Megiddo, N. ♦ Hakimi, S. L. ♦ Garey, M. R. ♦ Johnson, D. S. ♦ Papadimitriou, C. H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph $\textit{G}$ in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number $\textit{s}(\textit{G})$ of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether $\textit{s}(\textit{G})$ ≤ $\textit{K},$ for a given integer $\textit{K},$ is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs $\textit{G}$ with $\textit{s}(\textit{G})$ ≤ $\textit{K}$ for $\textit{K}$ = 1, 2, 3.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 1
Page Count 27
Starting Page 18
Ending Page 44

Open content in new tab

   Open content in new tab
Source: ACM Digital Library