Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

Cited In (49)

A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
Vertex Cover in Graphs with Locally Few Colors
New complexity results for the $k$-covers problem
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Randomized approximation for the set multicover problem in hypergraphs
A primal-dual approximation algorithm for \textsc{minsat}
Algorithms and Computation
An approximation algorithm for submodular hitting set problem with linear penalties
Minimum vertex cover in rectangle graphs
On the weighted $k$-path vertex cover problem
Title not available (Why is that?)
On the Lovász Theta Function for Independent Sets in Sparse Graphs
Polynomial kernelizations for MIN $F^{+}\Pi _{1}$ and MAX NP
Combinatorial Auctions with Conflict-Based Externalities
Improved approximation bounds for edge dominating set in dense graphs
An improved approximation algorithm for vertex cover with hard capacities
On the approximability and hardness of minimum topic connected overlay and its special instances
Independent sets in bounded-degree hypergraphs
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
On approximation of the vertex cover problem in hypergraphs
Ultimate greedy approximation of independent sets in subcubic graphs
The ordered covering problem
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
A primal-dual method for approximating tree cover with two weights
The power of amortized recourse for online graph problems
On the Minimum Hitting Set of Bundles Problem
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
Approximation algorithm for stochastic set cover problem
Vertex cover might be hard to approximate to within $2 - \varepsilon $
Greedy $\varDelta $-approximation algorithm for covering with arbitrary constraints and submodular cost
Local search with edge weighting and configuration checking heuristics for minimum vertex cover
On the minimum hitting set of bundles problem
Strong and weak edges of a graph and linkages with the vertex cover problem
An edge-reduction algorithm for the vertex cover problem
Reconstruction of Kauffman networks applying trees
New tools and connections for exponential-time approximation
Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014.
Improved non-approximability results for minimum vertex cover with density constraints
Nearly tight approximation bounds for vertex cover on dense $k$-uniform $ k$-partite hypergraphs
Models of greedy algorithms for graph problems
Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
The Approximability of Assortment Optimization Under Ranking Preferences
Approximation of set multi-cover via hypergraph matching
Approximating vertex cover in dense hypergraphs
Graph covering using bounded size subgraphs
Title not available (Why is that?)
Undercover: a primal MINLP heuristic exploring a largest sub-MIP

This page was built for publication: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

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