| Author(s) |
Brankovic, Ljiljana
Fernau, Hening
|
| Publication Date |
2010
|
| Abstract |
<p>We explore opportunities for parameterising constant factor approximation algorithms for vertex cover. We provide a simple algorithm that works on any approximation ratio of the form and has complexity that outperforms an algorithm by Bourgeois et al. derived from a sophisticated exact parameterised algorithm. In particular, for l=1 (factor 1.5 approximation) our algorithm runs in time. Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree four.</p>
|
| Citation |
21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, v.6506, p. 390-402
|
| ISBN |
978-3-642-17516-9
978-3-642-17517-6
|
| ISSN |
0302-9743
1611-3349
|
| Link | |
| Language |
en
|
| Publisher |
Springer
|
| Series |
Lecture Notes in Computer Science
|
| Title |
Combining Two Worlds: Parameterised Approximation for Vertex Cover
|
| Type of document |
Conference Publication
|
| Entity Type |
Publication
|
| Name | Size | format | Description | Link |
|---|