A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
From MaRDI portal
Publication:392028
DOI10.1016/j.tcs.2012.12.003zbMath1407.68542OpenAlexW2094388041MaRDI QIDQ392028
Henning Fernau, Ljiljana Brankovic
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.003
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (10)
Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Invited talks ⋮ The many facets of upper domination ⋮ On the Complexity Landscape of the Domination Chain ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exact exponential algorithms.
- Hardness results for approximating the bandwidth
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Improved upper bounds for vertex cover
- On the hardness of approximating minimum vertex cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- Efficient bounds for the stable set, vertex cover and set packing problems
- Some APX-completeness results for cubic graphs
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- On the existence of subexponential parameterized algorithms
- One for the price of two: a unified approach for approximating covering problems
- Fixed-parameter approximation: conceptual framework and approximability results
- An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex Cover: Further Observations and Further Improvements
- Parameterized Approximation via Fidelity Preserving Transformations
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Maximum-Minimum Sätze über Graphen
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- On Parameterized Approximability
- A Note on Vertex Cover in Graphs with Maximum Degree 3
- Confronting hardness using a hybrid approach
- Measure and conquer
- Searching Trees: An Essay
- Algorithms for maximum independent sets
- Approximation algorithms for NP-complete problems on planar graphs
- On efficient fixed-parameter algorithms for weighted vertex cover
- New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set
- Reducibility among Combinatorial Problems
- On approximation properties of the Independent set problem for degree 3 graphs
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- Vertex Cover Approximations on Random Graphs
- Experimental and Efficient Algorithms
- MAX SAT approximation beyond the limits of polynomial-time approximation
This page was built for publication: A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
