On conditional covering problem

DOI10.1007/s11786-009-0001-1zbMath1205.05229MaRDI QIDQ626967

C. Pandu Rangan, Balasubramanian Sivan, Sri Harini

Publication date: 19 February 2011

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-009-0001-1

zbMATH Keywords

paths; facility location; interval graphs; conditional covering problem; total domination problem

Mathematics Subject Classification ID

90C39: Dynamic programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

90B80: Discrete location and assignment

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

An efficient algorithm to solve the conditional covering problem on trapezoid graphs, Efficient algorithms for the conditional covering problem, The conditional covering problem on unweighted interval graphs with nonuniform coverage radius

Cites Work

• Unnamed Item
• Conditional covering: greedy heuristics and computational results
• Facility location on a tree with maximum distance constraints
• Domination and total domination on asteroidal triple-free graphs
• An Analysis of Network Location Problems with Distance Constraints
• Algorithms for solving the conditional covering problem on paths
• Dynamic programming algorithms for the conditional covering problem on path and extended star graphs
• A dynamic programming algorithm for the conditional covering problem on tree graphs