zbMATH — the first resource for mathematics

The complexity of searching a graph. (English) Zbl 0637.68081
The search number of a graph G, denoted by s(G), is the minimum number of seachers needed to guarantee the capture of an alien moving along the edge of G, who use perfect knowledge of searcher movement and unlimited speed to avoid capture. The present paper is likely to become a basic reference for those interested with this problem, since it contains a wealth of results and techniques concerning it. It is shown that given the graph G and the positive integer K, the problem “s(G)\(\leq K''\) is NP-complete. For the special case of G being a tree, the search number of G can be found in linear time. Structural characterizations of those graphs G with s(G)\(\leq K\) for \(K=1,2,3\) are also provided.
Reviewer: M.Zimand

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
Full Text: DOI