A note on the complexity of minimum dominating set

The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n   nodes is the trivial Ω(2n)Ω(2n) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a simple algorithm which solves this problem in O(1.81n)O(1.81n) time.