Some approximation algorithms for the clique partition problem in weighted interval graphs
- 作者：Mingxia Chen ; Jianbo Li ; Jianping Li ; Weidong Li ; Lusheng Wang
- 关键词：Weighted interval graphs ; Cliques ; Approximation algorithms
- 刊名：Theoretical Computer Science
- 出版年：2007
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：22 August 2007
- 卷：381
- 期：1-3
- 页码：124-133
- 文件大小：257 K
摘要
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 
miImageURL/B6V1G-4NKXWR9-1-3/0?wchp=dGLbVtb-zSkWW" alt="Click to view the MathML source" align="absbottom" border="0" height=9 width=21>-hard in a strong sense, and it cannot be approximated within a factor miImageURL/B6V1G-4NKXWR9-1-4/0?wchp=dGLbVtb-zSkWW" alt="Click to view the MathML source" align="absbottom" border="0" height=17 width=32> 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.