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 algorithmVertex coverCapacitated network design

Mathematics Subject Classification ID

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

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

(37)

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

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)