Approximating the dense set-cover problem

DOI10.1016/j.jcss.2004.03.006zbMath1109.68134OpenAlexW2075346653MaRDI QIDQ1765297

Zehavit Kehat, Reuven Bar Yehuda

Publication date: 23 February 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.03.006

zbMATH Keywords

Approximation algorithmSet-coverVertex-cover

Mathematics Subject Classification ID

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) Approximation algorithms (68W25)

Related Items

CLUSTAG & WCLUSTAG: Hierarchical Clustering Algorithms for Efficient Tag-SNP Selection ⋮ Approximating vertex cover in dense hypergraphs ⋮ Connected Vertex Covers in Dense Graphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Connected vertex covers in dense graphs ⋮ Approximating edge dominating set in dense graphs

Cites Work

• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Approximation algorithms for combinatorial problems
• An approximation of the minimum vertex cover in a graph
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item