Article ID Journal Published Year Pages File Type
431164 Journal of Discrete Algorithms 2006 6 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A note on the complexity of minimum dominating set
Authors
,