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
相关论文
共 50 条
  • [41] Exact algorithms for dominating set
    van Rooij, Johan M. M.
    Bodlaender, Hans L.
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (17) : 2147 - 2164
  • [42] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Chunmei Liu
    Yinglei Song
    Journal of Combinatorial Optimization, 2009, 18 : 87 - 97
  • [43] Approximating the Minimum Connected Dominating Set in Stochastic Graphs Based on Learning Automata
    Torkestani, J. Akbari
    Meybodi, M. R.
    2009 INTERNATIONAL CONFERENCE ON INFORMATION MANAGEMENT AND ENGINEERING, PROCEEDINGS, 2009, : 672 - +
  • [44] Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET
    Chinnasamy, A.
    Sivakumar, B.
    Selvakumari, P.
    Suresh, A.
    CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS, 2019, 22 (Suppl 5): : 12795 - 12804
  • [45] A local approximation algorithm for minimum dominating set problem in anonymous planar networks
    Wojciech Wawrzyniak
    Distributed Computing, 2015, 28 : 321 - 331
  • [46] A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
    Wawrzyniak, Wojciech
    INFORMATION PROCESSING LETTERS, 2014, 114 (03) : 94 - 98
  • [47] (6+ε)-approximation for minimum weight dominating set in unit disk graphs
    Gao, Xiaofeng
    Huang, Yaochun
    Zhang, Zhao
    Wu, Weili
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2008, 5092 : 551 - +
  • [48] A local approximation algorithm for minimum dominating set problem in anonymous planar networks
    Wawrzyniak, Wojciech
    DISTRIBUTED COMPUTING, 2015, 28 (05) : 321 - 331
  • [49] Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET
    A. Chinnasamy
    B. Sivakumar
    P. Selvakumari
    A. Suresh
    Cluster Computing, 2019, 22 : 12795 - 12804
  • [50] The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments
    Biswas, Arindam
    Jayapaul, Varunkumar
    Raman, Venkatesh
    Satti, Srinivasa Rao
    FRONTIERS IN ALGORITHMICS, FAW 2017, 2017, 10336 : 22 - 33
12345