Efficiency in exponential time for domination-type problems

We design fast exponential time algorithms for some intractable graph-theoretic problems. Our main result states that a minimum optional dominating set in a graph of order nn can be found in time O∗(1.8899n)O∗(1.8899n). Our methods to obtain this result involve matching techniques.The list of the considered problems includes Minimum Maximal Matching, 3-Colourability, Minimum Dominating Edge Set, Minimum Connected Dominating Set (∼Maximum Leaf Spanning Tree), Minimum Independent Dominating Set and Minimum Dominating set.