Improved approximation of maximum vertex cover

DOI10.1016/J.ORL.2005.03.006MaRDI QIDQ2583713zbMATH OpenOpenAlexFDO

Authors A. Galluccio, Paolo Nobili

Publication date 18 January 2006

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2005.03.006

zbMATH Keywords

approximation algorithmpolyhedravertex cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• On approximation of max-vertex-cover
• New approximation algorithms for the vertex cover problem
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem
• scientific article; zbMATH DE number 1445320
• Automata, Languages and Programming

Cites work

• A probabilistic analysis of the maximal covering location problem
• A threshold of ln n for approximating set cover
• Cardinality constrained path covering problems in grid graphs
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• On approximation of max-vertex-cover
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem

Cited in

(13)

• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• On approximation of max-vertex-cover
• Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
• Improved non-approximability results for minimum vertex cover with density constraints
• The maximum vertex coverage problem on bipartite graphs
• An improved approximation algorithm for vertex cover with hard capacities
• Vertex cover: Further observations and further improvements
• A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs
• New approximation algorithms for the vertex cover problem
• A better approximation ratio for the vertex cover problem
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• Automata, Languages and Programming

This page was built for publication: Improved approximation of maximum vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583713)