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