An Efficient Algorithm to Solve the Conditional Covering Problem on Trapezoid Graphs. (17th November 2011) - Rana, Akul; Pal, Anita; Pal, Madhumangal
Abstract : LetG = ( V, E ) be a simple connected undirected graph. Each vertexv ∈ V has a costc ( v ) and provides a positive coverage radiusR ( v ) . A distanced uv is associated with each edge u, v ∈ E, andd ( u, v ) is the shortest distance between every pair of verticesu, v ∈ V . A vertexv can cover all vertices that lie within the distanceR ( v ), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices inG . This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, anO ( n 2 ) time algorithm to solve a special case of the problem in a trapezoid graph is proposed, wheren is the number of vertices of the graph. In this special case, d uv = 1 for every edge u, v ∈ E, c ( v ) = c for everyv ∈ V ( G ), andR ( v ) = R, an integer >1, for everyv ∈ V ( G ) . A new data structure on trapezoid graphs is used to solve the problem.