A note on the complexity of minimum dominating set

被引：72
作者：
Grandoni, Fabrizio [1 ]
机构：
[1] Max Planck Inst Informatik, Stuhlsatzenhausweg 85, D-66123 Saarbrucken, Germany
来源：
JOURNAL OF DISCRETE ALGORITHMS | 2006年 / 4卷 / 02期
关键词：
Dominating set; Set cover; Exact algorithms;
D O I：
10.1016/j.jda.2005.03.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Omega(2(n)) 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.81(n)) time. (C) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：209 / 214
页数：6
相关论文
共 16 条
[11]   An improved exponential-time algorithm for k-SAT [J].
Paturi, R ;
Pudlák, P ;
Saks, ME ;
Zane, F .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :628-637
[12]  
Robson J.M., 2001, 125101 LABRI U BORD
[13]   ALGORITHMS FOR MAXIMUM INDEPENDENT SETS [J].
ROBSON, JM .
JOURNAL OF ALGORITHMS, 1986, 7 (03) :425-440
[14]  
Stein C, 2001, INTRO ALGORITHMS 2 V, Vsecond
[15]  
Tarjan R. E., 1977, SIAM Journal on Computing, V6, P537, DOI 10.1137/0206038
[16]  
[No title captured]
12