Approximation algorithm for vertex cover with multiple covering constraints

DOI10.1007/s00453-021-00885-wOpenAlexW3210112279MaRDI QIDQ2072095

Mong-Jen Kao, Eunpyeong Hung

Publication date: 1 February 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9991/

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for the partition vertex cover problem
• An analysis of the greedy algorithm for the submodular set covering problem
• On approximation of the submodular set cover problem
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Covering Problems with Hard Capacities
• Approximation algorithms for partial covering problems

This page was built for publication: Approximation algorithm for vertex cover with multiple covering constraints