Article ID: | iaor2014933 |
Volume: | 69 |
Issue: | 3 |
Start Page Number: | 685 |
End Page Number: | 740 |
Publication Date: | Jul 2014 |
Journal: | Algorithmica |
Authors: | Rooij Johan, Nederlof Jesper, Dijk Thomas |
Keywords: | optimization, programming: branch and bound |
Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential‐time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion‐based branching rule can be combined in a branch‐and‐reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times. In this way, we obtain the currently fastest exact exponential‐time algorithms for a number of domination problems in graphs. Among these are faster polynomial‐space and exponential‐space algorithms for