ISSN:
1432-0541
Keywords:
Key words. Graph searching problem, Edge searching, Node searching, Star-like graphs, Split graphs, Interval graphs.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 2 ) -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 , where m and n are the numbers of edges and vertices in the input graph, respectively. There is no polynomial algorithm known previously for any of the above problems. In addition, we also show that the edge-searching problem remains NP-complete on chordal graphs. For node searching, we give an O(mn k ) -time algorithm on k -starlike graphs for a fixed k \geq 1 . This result implies that the pathwidth problem on k -starlike graphs can also be solved in this time bound which greatly improves the previous results.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004530010026
Permalink
