A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
type: Item
instance of: scholarly article
title: A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
zbMATH Open document ID: 1407.68542
author: Ljiljana Brankovic
author: Henning Fernau
published in: Theoretical Computer Science
publication date: 2014-01-13T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6244631
zbMATH Keywords: parameterised algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: vertex cover
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.12.003
OpenAlex ID: W2094388041
cites work: Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
cites work: Some APX-completeness results for cubic graphs
cites work: Experimental and Efficient Algorithms
cites work: Vertex Cover Approximations on Random Graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: One for the price of two: a unified approach for approximating covering problems
cites work: On approximation properties of the Independent set problem for degree 3 graphs
cites work: An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
cites work: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
cites work: Combining Two Worlds: Parameterised Approximation for Vertex Cover
cites work: Fixed-parameter approximation: conceptual framework and approximability results
cites work: On the existence of subexponential parameterized algorithms
cites work: Refined memorization for vertex cover
cites work: Vertex cover: Further observations and further improvements
cites work: Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
cites work: Improved upper bounds for vertex cover
cites work: On Parameterized Approximability
cites work: MAX SAT approximation beyond the limits of polynomial-time approximation
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Kernels for the Vertex Cover Problem on the Preferred Attachment Model
cites work: On the hardness of approximating minimum vertex cover
cites work: Hardness results for approximating the bandwidth
cites work: New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set
cites work: Parameterized Approximation via Fidelity Preserving Transformations
cites work: Searching Trees: An Essay
cites work: Measure and conquer
cites work: Exact exponential algorithms.
cites work: Maximum-Minimum Sätze über Graphen
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Q3002852
cites work: Approximating vertex cover on dense graphs
cites work: A better approximation ratio for the vertex cover problem
cites work: Reducibility among Combinatorial Problems
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: A fine-grained analysis of a simple independent set algorithm
cites work: Q5710169
cites work: Q4251072
cites work: On efficient fixed-parameter algorithms for weighted vertex cover
cites work: Algorithms for maximum independent sets
cites work: Confronting hardness using a hybrid approach
cites work: A Note on Vertex Cover in Graphs with Maximum Degree 3
DOI: 10.1016/J.TCS.2012.12.003
description: scientific article; zbMATH DE number 6244631