Combining two worlds: parameterised approximation for vertex cover

Title: Combining two worlds: parameterised approximation for vertex cover
Creator: Brankovic, Ljiljana; Fernau, Henning
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
Publisher: Springer
Resource Type: conference paper
Date: 2010
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.
Subject: approximation algorithms; polynomial approximation; average degree; vertex cover
Identifier: http://hdl.handle.net/1959.13/935246
Identifier: uon:12013
Identifier: ISBN:9783642175169
Identifier: ISSN:0302-9743
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format