Approximating Subdense Instances of Covering Problems

DOI10.1016/j.endm.2011.05.051zbMath1268.68170arXiv1011.0078OpenAlexW1903530166MaRDI QIDQ2840726

Claus Viehmann, Jean Cardinal, Richard Schmied, Marek Karpinski

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.0078

zbMATH Keywords

graph coveringapproximation algorithmssubdense instances

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

On the approximability of dense Steiner problems ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Approximating edge dominating set in dense graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Connected vertex covers in dense graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Steiner trees in uniformly quasi-bipartite graphs.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The steiner problem in graphs
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems

This page was built for publication: Approximating Subdense Instances of Covering Problems