The Complexity of Searching a Graph (Preliminary Version)
The Complexity of Searching a Graph (Preliminary Version)
复制标题
搜索图的复杂性（初步版本）
DOI：
--
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou
中科院分区：
文献类型：
--
作者：
N. Megiddo;S. Hakimi;M. Garey;David S. Johnson;C. Papadimitriou
T. Parsons提出并部分分析了图上的追踪-逃避问题：一组搜索者遍历图G的边以追踪逃犯，逃犯在完全知道追踪者位置的情况下沿图的边沿着移动.什么是最小的搜索人数s（G），将足以保证捕获逃犯？我们证明，对于给定的整数K，确定s（G）≤ K对于一般图来说是NP难的，但对于树来说可以在线性时间内求解。给出了s（G）≤ K（K = 1，2，3）的图的结构特征.
T. Parsons proposed and partially analyzed the following pursuit-evasion problem on graphs: A team of searchers traverse the edges of a graph 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 s(G) of searchers that will suffice for guaranteeing capture of the fugitive? We show that determining whether s(G) ≤ K, for a given integer K, is NP-hard for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs with s(G) ≤ K for K = 1,2,3.