An Efficient Algorithm to Solve the Conditional Covering Problem on Trapezoid Graphs. (17th November 2011)

• Record Type: Journal Article
• Authors: Rana, Akul; Pal, Anita; Pal, Madhumangal
• Other Names: Gu Q. Academic Editor.; Rozikov U. A. Academic Editor.; Yeh R. Academic Editor.
• Is Part Of: ISRN discrete mathematics. Volume 2011(2011)
• Publication Date: 2011-11-17
• Subjects: Discrete mathematics -- Periodicals; Computer science -- Mathematics; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.5402/2011/213084
• Languages: English
• ISSNs: 2090-7788

Abstract

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.