Capacitated vertex covering

DOI10.1016/S0196-6774(03)00053-1MaRDI QIDQ4458880zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or

Publication date 14 March 2004

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(03)00053-1

zbMATH Keywords

Approximation algorithmCapacitated network designVertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 2119748
• scientific article; zbMATH DE number 2038708
• An improved approximation algorithm for vertex cover with hard capacities
• Covering Problems with Hard Capacities
• Approximation of Partial Capacitated Vertex Cover

Cited in

(39)

• Minimum-weight vertex cover problem for two-class resource connection graphs
• O(f) bi-criteria approximation for capacitated covering with hard capacities
• On approximation of max-vertex-cover
• The \((K, k)\)-capacitated spanning tree problem
• Approximating dynamic weighted vertex cover with soft capacities
• Algorithms and complexity results for the capacitated vertex cover problem
• Iterative partial rounding for vertex cover with hard capacities
• Facility location problems: a parameterized view
• Capacitated domination: problem complexity and approximation algorithms
• Capacitated Arc Stabbing
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Tight approximation for partial vertex cover with hard capacities
• A PTAS for the cardinality constrained covering with unit balls
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• The minimum generalized vertex cover problem
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• Covering Problems with Hard Capacities
• Capacitated Domination and Covering: A Parameterized Perspective
• Hitting diamonds and growing cacti
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• scientific article; zbMATH DE number 2038708 (Why is no real title available?)
• scientific article; zbMATH DE number 2119748 (Why is no real title available?)
• Analysis of a first-fit algorithm for the capacitated unit covering problem
• An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
• Algorithmic applications of tree-cut width
• Tight approximation for partial vertex cover with hard capacities
• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• The multi‐integer set cover and the facility terminal cover problem
• Capacitated domination problem
• Capacitated Domination Problem
• Approximation of Partial Capacitated Vertex Cover
• Capacitated discrete unit disk cover
• Optimizing server placement in distributed systems in the presence of competition
• Public goods in networks with constraints on sharing
• Online multiset submodular cover
• Approximation algorithm for prize-collecting vertex cover with fairness constraints
• Minimum-cost mixed graph covers with targeted weight constraints
• Online unit clustering: Variations on a theme
• A mixed integer linear program and tabu search approach for the complementary edge covering problem

This page was built for publication: Capacitated vertex covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458880)