Graph searching on some subclasses of chordal graphs

S. L. Peng, M. T. Ko, C. W. Ho, T. S. Hsu, C. Y. Tang

研究成果: 雜誌貢獻期刊論文同行評審

25 引文 斯高帕斯(Scopus)

摘要

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 0(mn2)-time algorithm on split graphs (i.e., 1-starlike graphs), an O(m + n)-time algorithm on interval graphs, and an O(mnk)-time algorithm on k-starlike graphs (a generalization of split graphs), for a fixed k ≥ 2, where m and n a 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(mnk)-time algorithm on k-starlike graphs for a fixed k ≥ 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.

原文???core.languages.en_GB???
頁(從 - 到)395-426
頁數32
期刊Algorithmica (New York)
27
發行號3-4
DOIs
出版狀態已出版 - 2000

指紋

深入研究「Graph searching on some subclasses of chordal graphs」主題。共同形成了獨特的指紋。

引用此