Grandoni, Fabrizio (2006) A note on the complexity of minimum dominating set. Journal of Discrete Algorithms, 4 (2). pp. 209-214. ISSN 1570-8667
|
Text
1-s2.0-S1570866705000225-main.pdf - Published Version Download (94kB) | Preview |
Official Website: http://dx.doi.org/10.1016/j.jda.2005.03.002
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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Dominating set; Set cover; Exact algorithms |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 09:12 |
| Last Modified: | 24 May 2016 06:05 |
| URI: | http://repository.supsi.ch/id/eprint/4518 |
Actions (login required)
 |
View Item |