Capacitated vertex covering
From MaRDI portal
Publication:4458880
DOI10.1016/S0196-6774(03)00053-1zbMath1079.68074OpenAlexW2051169745MaRDI QIDQ4458880
Refael Hassin, Einat Or, Sudipto Guha, Samir Khuller
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
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) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Capacitated Arc Stabbing ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ A primal-dual approximation algorithm for partial vertex cover: Making educated guesses ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Optimizing server placement in distributed systems in the presence of competition ⋮ Unnamed Item ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Capacitated Domination Problem ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Online unit clustering: Variations on a theme ⋮ A mixed integer linear program and tabu search approach for the complementary edge covering problem ⋮ Capacitated domination problem ⋮ Facility location problems: a parameterized view ⋮ Capacitated discrete unit disk cover ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Capacitated domination: problem complexity and approximation algorithms
This page was built for publication: Capacitated vertex covering