The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

摘要

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ∈ V. In the conditional covering problem, a vertex x ∈ V covers a vertex y ∈ V (x ≠ = y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C ∩ V so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n~2) time, when G is an interval graph containing n vertices.