Some approximation algorithms for the clique partition problem in weighted interval graphs
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 124-133 |
Journal / Publication | Theoretical Computer Science |
Volume | 381 |
Issue number | 1-3 |
Publication status | Published - 22 Aug 2007 |
Link(s)
Abstract
Interval graphs play important roles in analysis of DNA chains in Benzer [S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1959) 1607-1620], restriction maps of DNA in Waterman and Griggs [M.S. Waterman, J.R. Griggs, Interval graphs and maps of DNA, Bulletin of Mathematical Biology 48 (2) (1986) 189-195] and other related areas. In this paper, we study a new combinatorial optimization problem, named the minimum clique partition problem with constrained bounds, in weighted interval graphs. For a weighted interval graph G and a bound B, partition the weighted intervals of this graph G into the smallest number of cliques, such that each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond B. We obtain the following results: (1) this problem is NP-hard in a strong sense, and it cannot be approximated within a factor frac(3, 2) - ε in polynomial time for any ε > 0; (2) we design three approximation algorithms with different constant factors for this problem; (3) for the version where all intervals have the same weights, we design an optimal algorithm to solve the problem in linear time. © 2007 Elsevier Ltd. All rights reserved.
Research Area(s)
- Approximation algorithms, Cliques, Weighted interval graphs
Citation Format(s)
Some approximation algorithms for the clique partition problem in weighted interval graphs. / Chen, Mingxia; Li, Jianbo; Li, Jianping et al.
In: Theoretical Computer Science, Vol. 381, No. 1-3, 22.08.2007, p. 124-133.
In: Theoretical Computer Science, Vol. 381, No. 1-3, 22.08.2007, p. 124-133.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review