Brankovic, Ljiljana

Fernau, Hening

2010

<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>

21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, v.6506, p. 390-402

978-3-642-17516-9

978-3-642-17517-6

0302-9743

1611-3349

https://hdl.handle.net/1959.11/62028

Springer

Lecture Notes in Computer Science

Combining Two Worlds: Parameterised Approximation for Vertex Cover

Conference Publication

Publication