A note on the complexity of minimum dominating set

Balasubramanian, 1998, An improved fixed-parameter algorithm for vertex cover, Inform. Process. Lett., 65, 163, 10.1016/S0020-0190(97)00213-5 Bansal, 1999, Upper bounds for MaxSat: further improved Beigel, 1999, Finding maximum independent sets in sparse and general graphs, 856 Beigel, 1995, 3-coloring in time O(1.3446n): a no-MIS algorithm, 444 Chen, 2001, Vertex cover: further observations and further improvements, J. Algorithms, 41, 280, 10.1006/jagm.2001.1186 Cormen, 1990 Dantsin, 2002, A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search, Theoret. Comput. Sci., 289, 69, 10.1016/S0304-3975(01)00174-8 Eppstein, 2001, Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction, 329 Garey, 1979 Jian, 1986, An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans. Comput., 35, 847, 10.1109/TC.1986.1676847 Niedermeier, 2000, New upper bounds for maximum satisfiability, J. Algorithms, 36, 63, 10.1006/jagm.2000.1075 Niedermeier, 2003, On efficient fixed-parameter algorithms for weighted vertex cover, J. Algorithms, 47, 63, 10.1016/S0196-6774(03)00005-1 Paturi, 1998, An improved exponential-time algorithm for k-SAT, 628 Robson, 1986, Algorithms for maximum independent sets, J. Algorithms, 7, 425, 10.1016/0196-6774(86)90032-5 J.M. Robson, Finding a maximum independent set in time O(2n/4), Technical Report 1251-01, LaBRI, Université Bordeaux I, 2001 Tarjan, 1977, Finding a maximum independent set, SIAM J. Comput., 6, 537, 10.1137/0206038