Graph searching on some subclasses of chordal graphs

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

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

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 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.

Original languageEnglish
Pages (from-to)395-426
Number of pages32
JournalAlgorithmica (New York)
Volume27
Issue number3-4
DOIs
StatePublished - 2000

Keywords

  • Edge searching
  • Graph searching problem
  • Interval graphs
  • Node searching
  • Split graphs
  • Star-like graphs

Fingerprint

Dive into the research topics of 'Graph searching on some subclasses of chordal graphs'. Together they form a unique fingerprint.

Cite this