A note on the complexity of minimum dominating set

被引：71

作者：

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 条

[1] An improved fixed-parameter algorithm for vertex cover [J].

Balasubramanian, R ;

Fellows, MR ;

Raman, V .

INFORMATION PROCESSING LETTERS, 1998, 65 (03) :163-168

[2]

Beigel R, 1995, AN S FDN CO, P444

[3]

BEIGEL R, 1999, P 10 ACM SIAM S DISC, P856

[4] Vertex Cover: Further observations and further improvements [J].

Chen, J ;

Kanj, IA ;

Jia, WJ .

JOURNAL OF ALGORITHMS, 2001, 41 (02) :280-301

[5] A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search [J].

Dantsin, E ;

Goerdt, A ;

Hirsch, EA ;

Kannan, R ;

Kleinberg, J ;

Papadimitriou, C ;

Raghavan, P ;

Schöning, U .

THEORETICAL COMPUTER SCIENCE, 2002, 289 (01) :69-83

[6]

Eppstein D, 2001, SIAM PROC S, P329

[7]

Garey M.R., 1979, COMPUTERS INTRACTABI

[8]

JIAN T, 1986, IEEE T COMPUT, V35, P847, DOI 10.1109/TC.1986.1676847

[9] On efficient fixed-parameter algorithms for weighted vertex cover [J].

Niedermeier, R ;

Rossmanith, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 47 (02) :63-77

[10] New upper bounds for maximum satisfiability [J].

Niedermeier, R ;

Rossmanith, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 36 (01) :63-88

← 1 2 →