Jianping Li

Mingxia Chen 1, Jianbo Li 2, Jianping Li 3, Weidong Li 3, and Lusheng Wang 4
1 Department of Science and Technology, Yunnan University, Kunming 650091, P. R. China
2 School of Management and Economics, Kunming University of Science and Technology, Kunming 650090, P. R. China
3 Department of Mathematics, Yunnan University, Kunming 650091, P. R. China
4 Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong, P. R. China

Interval graphs play important roles in analysis of {\it DNA} chains in Benzer~\cite{Benzer}, restriction maps of {\it DNA} in Waterman and Griggs \cite{Waterman} and other related areas. In this paper, we study a new combinatorial optimization problem, named as the minimum clique partition problem with constrained weight, for 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, where 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 the strong sense, and it cannot be approximated within a ratio $\frac{3}{2}-\varepsilon$ in polynomial-time for any $\varepsilon >0$; (2) We design some approximation algorithms with different constant ratios to this problem; (3) For the case where all intervals have the same weight, we also design an optimal algorithm to solve the problem in linear time.