A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
From MaRDI portal
Publication:392028
Recommendations
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- New approximation algorithms for the vertex cover problem
- An improved fixed-parameter algorithm for vertex cover
- Saving on phases: parameterized approximation for total vertex cover
- Maximum minimal vertex cover parameterized by vertex cover
Cites work
- A better approximation ratio for the vertex cover problem
- A fine-grained analysis of a simple independent set algorithm
- A note on vertex cover in graphs with maximum degree 3
- Algorithms for maximum independent sets
- An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
- Approximating vertex cover on dense graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for NP-hard problems.
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Confronting hardness using a hybrid approach
- Efficient bounds for the stable set, vertex cover and set packing problems
- Exact exponential algorithms.
- Experimental and Efficient Algorithms
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Fixed-parameter approximation: conceptual framework and approximability results
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Hardness results for approximating the bandwidth
- scientific article; zbMATH DE number 1304341 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Improved upper bounds for vertex cover
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Maximum-Minimum Sätze über Graphen
- Measure and conquer
- New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
- On approximation properties of the Independent set problem for degree 3 graphs
- On efficient fixed-parameter algorithms for weighted vertex cover
- On Parameterized Approximability
- On the existence of subexponential parameterized algorithms
- On the hardness of approximating minimum vertex cover
- One for the price of two: a unified approach for approximating covering problems
- Parameterized approximation via fidelity preserving transformations
- Reducibility among combinatorial problems
- Refined memorization for vertex cover
- Searching Trees: An Essay
- Some APX-completeness results for cubic graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Vertex Cover Approximations on Random Graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex cover: Further observations and further improvements
Cited in
(21)- Parameterized approximation via fidelity preserving transformations
- The many facets of upper domination
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Invited talks
- On the complexity landscape of the domination chain
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Parameterized approximation via fidelity preserving transformations
- Saving on phases: parameterized approximation for total vertex cover
- Maximum minimal vertex cover parameterized by vertex cover
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- scientific article; zbMATH DE number 5631194 (Why is no real title available?)
- Maximum minimal vertex cover parameterized by vertex cover
- Parameterized approximation algorithms for weighted vertex cover
- Parameterized algorithms for minimum sum vertex cover
- Parameterized approximation algorithms for weighted vertex cover
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
- Faster exponential-time approximation algorithms using approximate monotone local search
- Parameterized approximation scheme for feedback vertex set
- Sampling with a black box: faster parameterized approximation algorithms for vertex deletion problems
- Data reductions and combinatorial bounds for improved approximation algorithms
This page was built for publication: A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392028)
