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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBrankovic, Ljiljanaen
dc.contributor.authorFernau, Heningen
dc.date.accessioned2024-08-08T03:19:15Z-
dc.date.available2024-08-08T03:19:15Z-
dc.date.issued2010-
dc.identifier.citation21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, v.6506, p. 390-402en
dc.identifier.isbn978-3-642-17516-9en
dc.identifier.isbn978-3-642-17517-6en
dc.identifier.issn0302-9743en
dc.identifier.issn1611-3349en
dc.identifier.urihttps://hdl.handle.net/1959.11/62028-
dc.description.abstract<p>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.</p>en
dc.languageenen
dc.publisherSpringeren
dc.relation.ispartof21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part Ien
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.titleCombining Two Worlds: Parameterised Approximation for Vertex Coveren
dc.typeConference Publicationen
dc.relation.conferenceISAAC 2010: 21st Annual International Symposium on Algorithms and Computations (ISAAC)en
dc.identifier.doi10.1007/978-3-642-17517-6_35en
local.contributor.firstnameLjiljanaen
local.contributor.firstnameHeningen
local.profile.schoolSchool of Science and Technologyen
local.profile.emaillbrankov@une.edu.auen
local.output.categoryE1en
local.record.placeauen
local.record.institutionUniversity of New Englanden
local.date.conference15th to 17th of December, 2010en
local.conference.placeJeju Island, Korea (Republic of)en
local.publisher.placeUnited States of Americaen
local.format.startpage390en
local.format.endpage402en
local.series.number6506en
local.identifier.volume6506en
local.title.subtitleParameterised Approximation for Vertex Coveren
local.contributor.lastnameBrankovicen
local.contributor.lastnameFernauen
dc.identifier.staffune-id:lbrankoven
local.profile.orcid0000-0002-5056-4627en
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/62028en
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleCombining Two Worldsen
local.output.categorydescriptionE1 Refereed Scholarly Conference Publicationen
local.conference.detailsISAAC 2010: 21st Annual International Symposium on Algorithms and Computations (ISAAC), Jeju Island, Korea (Republic of), 15th to 17th of December, 2010en
local.search.authorBrankovic, Ljiljanaen
local.search.authorFernau, Heningen
local.uneassociationNoen
local.atsiresearchNoen
local.sensitive.culturalNoen
local.year.published2010en
local.subject.for2020461305 Data structures and algorithmsen
local.subject.seo2020220499 Information systems, technologies and services not elsewhere classifieden
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
Appears in Collections:Conference Publication
School of Science and Technology
Show simple item record

SCOPUSTM   
Citations

12
checked on Dec 14, 2024
Google Media

Google ScholarTM

Check

Altmetric


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