A note on the complexity of minimum dominating set |
| |
| Authors: | Fabrizio Grandoni |
| |
| Affiliation: | Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany |
| |
| Abstract: | ![]()
The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Ω(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) time. |
| |
| Keywords: | Dominating set Set cover Exact algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
