1. On the interval completion of chordal graphs
- Author
-
Peng, Sheng-Lung and Chen, Chi-Kang
- Subjects
- *
GRAPH theory , *COMPUTATIONAL biology , *HUMAN fingerprints , *BIOINFORMATICS - Abstract
Abstract: For a given graph , the interval completion problem of G is to find an edge set F such that the supergraph of G is an interval graph and is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF