The Conditional Covering Problem on Interval Graphs with Unequal Costs

10.6988/TOJIMS.201105.0183

Akul Rana；Anita Pal；Madhumangal Pal

Design of algorithms ； Analysis of algorithms ； Interval graph ； Set covering ； Conditional covering

Tamsui Oxford Journal of Information and Mathematical Sciences

27卷2期（2011 / 05 / 01）

183 - 195

英文

The conditional covering problem is an extension of classical set covering problem. The classical set covering problem finds a minimum cost covering set that covers all the vertices of the graph. The conditional covering problem has the same objective with an additional condition that every vertex in the covering set must be cover by at least one other vertex in the covering set. This problem is known to be NP-hard for general graphs. In some special cases, polynomial results are known. In this paper, an O(n^2) time algorithm is presented to compute the minimum cost conditional covering set of an interval graph with n vertices. Here it is assumed that the costs of the vertices are unequal. The dynamic programming approach is used to solve the problem.