- Title
- Breaking the 2ⁿ-barrier for irredundance: two lines of attack
- Creator
- Binkele-Raible, Daniel; Brankovic, Ljiljana; Wojtaszczyk, Jakub Onufry; Cygan, Marek; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Pilipczuk, Marcin; Rossmanith, Peter
- Relation
- Journal of Discrete Algorithms Vol. 9, Issue 3, p. 214-230
- Publisher Link
- http://dx.doi.org/10.1016/j.jda.2011.03.002
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2011
- Description
- 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 Θ(2ⁿ·poly(n)) enumeration, also called the 2ⁿ-barrier. The main contributions of this article are exact exponential-time algorithms breaking the 2ⁿ-barrier for irredundance. We establish algorithms with running times of O*(1.99914ⁿ) for computing ir(G) and O* (1.9369ⁿ) 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.
- Subject
- graph algorithms; irredundance number; graph parameters; 2ⁿ-barrier
- Identifier
- http://hdl.handle.net/1959.13/936224
- Identifier
- uon:12245
- Identifier
- ISSN:1570-8667
- Language
- eng
- Reviewed
- Hits: 10510
- Visitors: 6920
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|