查看文章

In the graph-searching problem, initially a graph with all the edges contaminated is presented. The objective is to obtain a state of the graph in which all the edges are simultaneously cleared by using the least number of searchers. Two variations of the graph-searching problem are considered. One is edge searching, in which an edge is cleared by moving a searcher along this edge, and the other is node searching, in which an edge is cleared by concurrently having searchers on both of its two endpoints.

We present a uniform approach to solve the above two variations on several subclasses of chordal graphs. For edge searching, we give an O(mn ² ) -time algorithm on split graphs (i.e., 1-starlike graphs), an O(m+n) -time algorithm on interval graphs, and an O(mn ^k ) -time algorithm on k -starlike graphs (a generalization of split graphs), for a fixed k\geq 2 …