Combining Two Worlds: Parameterised Approximation for Vertex Cover

Title
Combining Two Worlds: Parameterised Approximation for Vertex Cover
Publication Date
2010
Author(s)
Brankovic, Ljiljana
( author )
OrcID: https://orcid.org/0000-0002-5056-4627
Email: lbrankov@une.edu.au
UNE Id une-id:lbrankov
Fernau, Hening
Type of document
Conference Publication
Language
en
Entity Type
Publication
Publisher
Springer
Place of publication
United States of America
Series
Lecture Notes in Computer Science
DOI
10.1007/978-3-642-17517-6_35
UNE publication id
une:1959.11/62028
Abstract

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.

Link
Citation
21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, v.6506, p. 390-402
ISSN
0302-9743
1611-3349
ISBN
978-3-642-17516-9
978-3-642-17517-6
Start page
390
End page
402

Files:

NameSizeformatDescriptionLink