Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421053 | Discrete Applied Mathematics | 2006 | 8 Pages |
Abstract
For a given graph G=(V,E)G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F)H=(V,E∪F) of G is an interval graph and |F||F| 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sheng-Lung Peng, Chi-Kang Chen,