Combining two worlds: parameterised approximation for vertex cover | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/935246

Title: Combining two worlds: parameterised approximation for vertex cover
Author/Creator: Brankovic, Ljiljana; Fernau, Henning
Institution: The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description: 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 2ι+1/ι+1 and has complexity that outperforms an algorithm by Bourgeois et al. derived from a sophisticated exact parameterised algorithm. In particular, for ι = 1 (factor 1.5 approximation) our algorithm runs in time O*(1.09^k). Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree four.
Relation: 21st International Symposium on Algorithms and Computation (ISAAC 2010). Algorithms and Computation: Proceedings of the 21st International Symposium (ISAAC 2010), Part 1 (Jeju Island, Korea 15-17 December, 2010) p. 390-402
Publisher Link: http://dx.doi.org/10.1007/978-3-642-17517-6_35
Date: 2010
Publisher: Springer
Keyword(s): approximation algorithms; polynomial approximation; average degree; vertex cover
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/935246
Identifier: ISBN:9783642175169
Identifier: ISSN:0302-9743

5 Visitors

6 Hits

NOVA. The University of Newcastle's Digital Repository