篇名 | The Conditional Covering Problem on Interval Graphs with Unequal Costs |
---|---|
卷期 | 27:2 |
作者 | Akul Ranay 、 Anita Palz 、 Madhumangal Palx |
頁次 | 183-195 |
關鍵字 | Design of algorithms 、 Analysis of algorithms 、 In-terval graph 、 Set covering 、 Conditional covering |
出刊日期 | 201105 |
The conditional covering problem is an extension of classical set cov-ering 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(n2) time algorithm is presented to compute the minimum cost conditional covering set of an interval graph with n ver-tices. Here it is assumed that the costs of the vertices are unequal. The dynamic programming approach is used to solve the problem.