A better approximation ratio for the vertex cover problem

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (34)

A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
Vertex cover in conflict graphs
Timeline cover in temporal graphs: exact and approximation algorithms
Vertex Cover in Graphs with Locally Few Colors
Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover
A parameterized approximation scheme for generalized partial vertex cover
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
Approximating Partially Bounded Degree Deletion on Directed Graphs
On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
Title not available (Why is that?)
Approximating power node-deletion problems
Improved approximation algorithms for path vertex covers in regular graphs
Approximating power node-deletion problems
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
The ordered covering problem
From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
The power of amortized recourse for online graph problems
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
Some Inverse Traveling Salesman Problems
Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
Wireless capacity with arbitrary gain matrix
Reinforcement learning for combinatorial optimization: a survey
Strong and weak edges of a graph and linkages with the vertex cover problem
Approximation for vertex cover in \(\beta\)-conflict graphs
Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs
Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
Approximating vertex cover in dense hypergraphs
Approximating Bounded Degree Deletion via Matroid Matching
Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
Undercover: a primal MINLP heuristic exploring a largest sub-MIP

This page was built for publication: A better approximation ratio for the vertex cover problem

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