| Title |
|
Breaking the 2n-barrier for Irredundance: Two lines of attack |
|
|
| Publication Date |
|
| Author(s) |
|
Wojtaszczyk, Jakub Onufry |
|
|
| Type of document |
|
| Language |
|
| Entity Type |
|
| Publisher |
|
| Place of publication |
|
| DOI |
|
10.1016/j.jda.2011.03.002 |
|
|
| UNE publication id |
|
| Abstract |
The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G), 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 G on n vertices admits exact algorithms running in time faster than the trivial Θ(2n · poly(n)) enumeration, also called the 2n-barrier. The main contributions of this article are exact exponential-time algorithms breaking the 2n-barrier for irredundance. We establish algorithms with running times of O*(1.99914n) for computing ir(G) and O*(1.9369n) for computing IR(G). 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. |
|
|
| Link |
|
| Citation |
|
Journal of Discrete Algorithms, 9(3), p. 214-230 |
|
|
| ISSN |
|
| Start page |
|
| End page |
|