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