Author(s) |
Binkele-Raible, Daniel
Brankovic, Ljiljana
Cygan, Marek
Fernau, Henning
Kneis, Joachim
Kratsch, Dieter
Langer, Alexander
Liedloff, Mathieu
Pilipczuk, Marcin
Rossmanith, Peter
Wojtaszczyk, Jakub Onufry
|
Publication Date |
2011-09
|
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 the domination and independence numbers and have numerous relations to other graph parameters. It has been an open question whether determining these numbers for a graph <i>G</i> on <i>n</i> vertices admits exact algorithms running in time faster than the trivial Θ(<i>2<sup>n</sup></i> · poly(<i>n</i>)) enumeration, also called the <i>2<sup>n</sup></i>-barrier. The main contributions of this article are exact exponential-time algorithms breaking the <i>2<sup>n</sup></i>-barrier for irredundance. We establish algorithms with running times of <i>O<sup>*</sup></i>(1.99914<sup><i>n</i></sup>) for computing ir(<i>G</i>) and <i>O<sup>*</sup></i>(1.9369<sup><i>n</i></sup>) for computing IR(<i>G</i>). Both algorithms use polynomial space. The first algorithm uses a parameterized approach to obtain (faster) exact algorithms. The second one is based, in addition, on a reduction to the Maximum Induced Matching problem providing a branch-and-reduce algorithm to solve it.</p>
|
Citation |
Journal of Discrete Algorithms, 9(3), p. 214-230
|
ISSN |
1570-8675
1570-8667
|
Link | |
Publisher |
Elsevier BV
|
Title |
Breaking the 2n-barrier for Irredundance: Two lines of attack
|
Type of document |
Journal Article
|
Entity Type |
Publication
|
Name | Size | format | Description | Link |
---|