1. Research UNE
  2. UNE
  3. Conference Publication
Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/62028
Title: Combining Two Worlds: Parameterised Approximation for Vertex Cover
Contributor(s): Brankovic, Ljiljana  (author)orcid ; Fernau, Hening (author)
Publication Date: 2010
DOI: 10.1007/978-3-642-17517-6_35
Handle Link: https://hdl.handle.net/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.

Publication Type: Conference Publication
Conference Details: ISAAC 2010: 21st Annual International Symposium on Algorithms and Computations (ISAAC), Jeju Island, Korea (Republic of), 15th to 17th of December, 2010
Source of Publication: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, v.6506, p. 390-402
Publisher: Springer
Place of Publication: United States of America
ISSN: 0302-9743
1611-3349
Fields of Research (FoR) 2020: 461305 Data structures and algorithms
Socio-Economic Objective (SEO) 2020: 220499 Information systems, technologies and services not elsewhere classified
HERDC Category Description: E1 Refereed Scholarly Conference Publication
Series Name: Lecture Notes in Computer Science
Series Number : 6506
Appears in Collections:Conference Publication
School of Science and Technology

Show full item record

SCOPUSTM   
Citations

12
checked on Nov 2, 2024
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.