Graph Searching and Interval Completion
Fedor V. Fomin, Petr A. Golovach · SIAM Journal on Discrete Mathematics · 2000
Inthe early studies on graph searching a graph was considered as a system of tunnels in which a fast and clever fugitive is hidden. The "classical" search problem is to find a search plan using the minimal number of searchers. In this paper, we consider a new criterion of optimization, namely, the search cost. First, we prove monotone properties of searching with the smallest cost. Then, making use of monotone properties, we prove that for any graph G the search cost of G is equal to the smallest number of edges of all interval supergraphs of G. Finally, we show how to compute the search cost of a cograph and the corresponding search strategy in linear time.