Author(s) |
Brankovic, Ljiljana
Fernau, Hening
|
Publication Date |
2013-11-04
|
Abstract |
<p>Parameterised approximation is a relatively new but growing field of interest. It merges two ways of dealing with NP-hard optimisation problems, namely polynomial approximation and exact parameterised (exponential-time) algorithms. We exemplify this idea by designing and analysing parameterised approximation algorithms for minimum vertex cover. More specifically, we provide a simple algorithm that works on any approximation ratio of the form 2l+1/l+1, l = 1, 2, . . ., and has complexity that outperforms previously published algorithms based on sophisticated exact parameterised algorithms. In particular, for l = 1 (factor-1.5 approximation) our algorithm runs in time O*(1.0883<sup><i>k</i></sup>), where parameter <i>k</i> ≤ 2/3<i>τ</i> , and <i>τ</i> is the size of a minimum vertex cover. Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree at most four and a limited number of vertices with degree less than two.</p>
|
Citation |
Theoretical Computer Science, v.511, p. 85-108
|
ISSN |
0304-3975
|
Link | |
Publisher |
Elsevier BV
|
Title |
A novel parameterised approximation algorithm for minimum vertex cover
|
Type of document |
Journal Article
|
Entity Type |
Publication
|
Name | Size | format | Description | Link |
---|