Capacitated Domination Problem

DOI10.1007/978-3-540-77120-3_24zbMath1193.05127OpenAlexW1495879230MaRDI QIDQ5387762

Mong-Jen Kao, Chung-Shou Liao

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_24

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-tuple domination in graphs
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Improved approximation algorithms for capacitated facility location problems
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• An improved approximation algorithm for vertex cover with hard capacities
• Approximation Algorithms for Metric Facility Location Problems
• Covering Problems with Hard Capacities
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Dependent rounding and its applications to approximation algorithms
• A new greedy approach for facility location problems
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Capacitated vertex covering
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Integer Programming and Combinatorial Optimization
• Algorithms - ESA 2003

This page was built for publication: Capacitated Domination Problem