Back to Search
Start Over
On the interval completion of chordal graphs
- Source :
-
Discrete Applied Mathematics . Apr2006, Vol. 154 Issue 6, p1003-1010. 8p. - Publication Year :
- 2006
-
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]
- Subjects :
- *GRAPH theory
*COMPUTATIONAL biology
*HUMAN fingerprints
*BIOINFORMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 154
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 20032771
- Full Text :
- https://doi.org/10.1016/j.dam.2005.09.010