Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/62031
Title: A Parameterized Route to Exact Puzzles: Breaking the 2n -Barrier for Irredundance
Contributor(s): Binkele-Raible, Daniel (author); Brankovic, Ljiljana  (author)orcid ; Fernau, Henning (author); Kneis, Joachim (author); Kratsch, Dieter (author); Langer, Alexander (author); Liedloff, Mathieu (author); Rossmanith, Peter (author)
Publication Date: 2010
DOI: 10.1007/978-3-642-13073-1_28
Handle Link: https://hdl.handle.net/1959.11/62031
Abstract: 

. The lower and the upper irredundance numbers of a graph G, denoted ir(G ) and IR(G ) 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 G on n vertices admits exact algorithms running in time less than the trivial Ω(2n) 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 O* (4k). For example, we present an algorithm running in time O* (3.069k) for determining whether IR(G ) is at least n − k . 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.

Publication Type: Conference Publication
Conference Details: CIAC 2010: 7th International Conference on Algorithms and Complexity, Rome, Italy, 26th - 28th May, 2010
Source of Publication: Algorithms and Complexity, p. 311-322
Publisher: Springer Berlin, Heidelberg
Place of Publication: Germany
Fields of Research (FoR) 2020: 461305 Data structures and algorithms
Socio-Economic Objective (SEO) 2020: 220499 Information systems, technologies and services not elsewhere classified
Peer Reviewed: Yes
HERDC Category Description: E1 Refereed Scholarly Conference Publication
Series Name: Lecture Notes in Computer Science
Series Number : 6078
Appears in Collections:Conference Publication
School of Science and Technology

Files in This Item:
2 files
File Description SizeFormat 
Show full 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.