Details

Autor(en) / Beteiligte

• Binkele-Raible, Daniel
• Brankovic, Ljiljana
• Cygan, Marek
• Fernau, Henning
• Kneis, Joachim
• Kratsch, Dieter
• Langer, Alexander
• Liedloff, Mathieu
• Pilipczuk, Marcin
• Rossmanith, Peter
• Wojtaszczyk, Jakub Onufry

Titel

Breaking the 2 n -barrier for Irredundance: Two lines of attack

Ist Teil von

• Journal of discrete algorithms (Amsterdam, Netherlands), 2011, Vol.9 (3), p.214-230

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2011

Link zum Volltext

Quelle

Elsevier ScienceDirect Journals Complete

Beschreibungen/Notizen

• 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 n ⋅ poly ( n ) ) enumeration, also called the 2 n -barrier. The main contributions of this article are exact exponential-time algorithms breaking the 2 n -barrier for irredundance. We establish algorithms with running times of O ⁎ ( 1.99914 n ) for computing ir ( G ) and O ⁎ ( 1.9369 n ) 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.