An exact algorithm for connected red–blue dominating set

Alber, 2000, Fixed parameter algorithms for planar dominating set and related problems, 97 A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, Fourier meets Möbius: Fast subset convolution, in: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 67–74. Blum, 2005, Connected dominating set in sensor networks and MANETs, 329 Dorn, 2005, Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, 95 Downey, 1997, Parameterized complexity: A framework for systematically confronting computational intractability, 49 Downey, 1999, The parametrized complexity of some fundamental problems in coding theory, SIAM J. Comput., 29, 545, 10.1137/S0097539797323571 H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible, P. Rossmanith, An exact algorithm for the maximum leaf spanning tree problem, in: Proceedings of the 4th International Workshop on Parameterized and Exact Computation IWPEC, 2009. F. Fomin, F. Grandoni, D. Kratsch, Measure and conquer: Domination – A case study, in: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, vol. 3580, 2004, pp. 191–203. Fomin, 2008, Solving connected dominating set faster than 2n, Algorithmica, 52, 153, 10.1007/s00453-007-9145-z Garey, 1990 I. Navid, Data reduction for connected dominating set, Master thesis, Simon Fraser University, 2005. Nederlof, 2009, Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner tree and related problems, 713 van Rooij, 2008, Design by measure and conquer, a faster exact algorithm for dominating set, vol. 1, 657 van Rooij, 2009, Inclusion/exclusion meets measure and conquer: Exact algorithms for counting dominating sets, 554