A novel parameterised approximation algorithm for minimum vertex cover

Title: A novel parameterised approximation algorithm for minimum vertex cover
Creator: Brankovic, Ljiljana; Fernau, Henning
Relation: Theoretical Computer Science Vol. 511, p. 85-108
Publisher Link: http://dx.doi.org/10.1016/j.tcs.2012.12.003
Publisher: Elsevier
Resource Type: journal article
Date: 2013
Description: 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), where parameter k ≤ 2/3t, and t 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.
Subject: parameterised algorithms; approximation algorithms; vertex cover
Identifier: http://hdl.handle.net/1959.13/1057767
Identifier: uon:16260
Identifier: ISSN:0304-3975
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format