Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/62031
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBinkele-Raible, Danielen
dc.contributor.authorBrankovic, Ljiljanaen
dc.contributor.authorFernau, Henningen
dc.contributor.authorKneis, Joachimen
dc.contributor.authorKratsch, Dieteren
dc.contributor.authorLanger, Alexanderen
dc.contributor.authorLiedloff, Mathieuen
dc.contributor.authorRossmanith, Peteren
dc.date.accessioned2024-08-08T03:59:39Z-
dc.date.available2024-08-08T03:59:39Z-
dc.date.issued2010-
dc.identifier.citationAlgorithms and Complexity, p. 311-322en
dc.identifier.isbn9783642130731en
dc.identifier.isbn9783642130724en
dc.identifier.urihttps://hdl.handle.net/1959.11/62031-
dc.description.abstract<p>. The lower and the upper irredundance numbers of a graph <i>G</i>, denoted ir(<i>G</i> ) and IR(<i>G</i> ) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph <i>G</i> on <i>n</i> vertices admits exact algorithms running in time less than the trivial <i>Ω</i>(2<sup><i>n</i></sup>) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than <i>O*</i> (4<sup><i>k</i></sup>). For example, we present an algorithm running in time <i>O*</i> (3.069<sup><i>k</i></sup>) for determining whether IR(<i>G</i> ) is at least <i>n − k</i> . Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.</p>en
dc.languageenen
dc.publisherSpringer Berlin, Heidelbergen
dc.relation.ispartofAlgorithms and Complexityen
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.titleA Parameterized Route to Exact Puzzles: Breaking the 2n -Barrier for Irredundanceen
dc.typeConference Publicationen
dc.relation.conferenceCIAC 2010: 7th International Conference on Algorithms and Complexityen
dc.identifier.doi10.1007/978-3-642-13073-1_28en
local.contributor.firstnameDanielen
local.contributor.firstnameLjiljanaen
local.contributor.firstnameHenningen
local.contributor.firstnameJoachimen
local.contributor.firstnameDieteren
local.contributor.firstnameAlexanderen
local.contributor.firstnameMathieuen
local.contributor.firstnamePeteren
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.conference26th - 28th May, 2010en
local.conference.placeRome, Italyen
local.publisher.placeGermanyen
local.format.startpage311en
local.format.endpage322en
local.series.issn1611-3349en
local.series.issn0302-9743en
local.series.number6078en
local.peerreviewedYesen
local.title.subtitleBreaking the 2n -Barrier for Irredundanceen
local.contributor.lastnameBinkele-Raibleen
local.contributor.lastnameBrankovicen
local.contributor.lastnameFernauen
local.contributor.lastnameKneisen
local.contributor.lastnameKratschen
local.contributor.lastnameLangeren
local.contributor.lastnameLiedloffen
local.contributor.lastnameRossmanithen
dc.identifier.staffune-id:lbrankoven
local.profile.orcid0000-0002-5056-4627en
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/62031en
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleA Parameterized Route to Exact Puzzlesen
local.output.categorydescriptionE1 Refereed Scholarly Conference Publicationen
local.conference.detailsCIAC 2010: 7th International Conference on Algorithms and Complexity, Rome, Italy, 26th - 28th May, 2010en
local.search.authorBinkele-Raible, Danielen
local.search.authorBrankovic, Ljiljanaen
local.search.authorFernau, Henningen
local.search.authorKneis, Joachimen
local.search.authorKratsch, Dieteren
local.search.authorLanger, Alexanderen
local.search.authorLiedloff, Mathieuen
local.search.authorRossmanith, Peteren
local.uneassociationNoen
local.atsiresearchNoen
local.conference.venueRome, Italyen
local.sensitive.culturalNoen
local.year.published2010en
local.fileurl.closedpublishedhttps://rune.une.edu.au/web/retrieve/64879910-8ccc-4719-8774-13d11c45fda1en
local.subject.for2020461305 Data structures and algorithmsen
local.subject.seo2020220499 Information systems, technologies and services not elsewhere classifieden
local.date.start2010-05-26-
local.date.end2010-05-28-
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
Appears in Collections:Conference Publication
School of Science and Technology
Files in This Item:
2 files
File Description SizeFormat 
Show simple item record

SCOPUSTM   
Citations

2
checked on Dec 7, 2024
Google Media

Google ScholarTM

Check

Altmetric


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