"Exact algorithms for MINIMUM DOMINATING SET"
Technical report by Bert Randerath, Ingo Schiermeyer, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Speckenmeyer
Preprint Key:	zaik2004-469
Keywords:	3-colourability, connected domination, domination, edge domination, exact algorithms, maximum leaf spanning tree
MSC codes:	05C15, 05C69, 68Q25, 68W01
This technical report has 8 pages, was written in April 2004, it has not been published.
Abstract:	We design exact algorithms for several NP-complete graph-theoretic problems. The term exact algorithm is a shorthand for a fast exponential time algorithm. Our main result states that a minimum dominating set in a graph of order n can be found in time O(1.8899^n). The list of considered problems includes MINIMUM DOMINATING SET, 3-COLOURABILITY, MINIMUM CONNECTED DOMINATING SET (~MAXIMUM LEAF SPANNING TREE), MINIMUM EDGE DOMINATING SET, MINIMUM INDEPENDENT DOMINATING SET and MINIMUM MAXIMAL MATCHING.