The probabilistic minimum dominating set problem

被引：4
|
作者：
Boria, Nicolas [1 ,2 ]
Murat, Cecile [1 ]
Paschos, Vangelis Th. [1 ]
机构：
[1] PSL Res Univ, Univ Paris Dauphine, CNRS, UMR 7243, F-75016 Paris, France
[2] Politecn Torino, Dipartimento Automat & Informat, Turin, Italy
来源：
DISCRETE APPLIED MATHEMATICS | 2018年 / 234卷
关键词：
Complexity; Approximation; Probabilistic optimization; Dominating set; Wireless sensor networks; TRAVELING SALESMAN PROBLEM; LOCAL SEARCH; OPTIMIZATION;
D O I：
10.1016/j.dam.2016.10.016
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present a natural wireless sensor network problem, which we model as a probabilistic version of the MIN DOMINATING SET problem (called PROBABILISTIC MIN DOMINATING SET). We first show that calculation of the objective function of this general probabilistic problem is #P-complete. We then introduce a restricted version of PROBABILISTIC MIN DOMINATING SET and show that, this time, calculation of its objective function can be performed in polynomial time and that this restricted problem is "just" NP-hard, since it is a generalization of the classical MIN DOMINATING SET. We study the complexity of this restricted version in graphs where MIN DOMINATING SET is polynomial, mainly in trees and paths and then we give some approximation results for it. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：93 / 113
页数：21
相关论文
共 50 条
  • [31] Hybrid metaheuristic algorithms for minimum weight dominating set
    Potluri, Anupama
    Singh, Alok
    APPLIED SOFT COMPUTING, 2013, 13 (01) : 76 - 88
  • [32] Approximating a Minimum Dominating Set by Purification
    Inza, Ernesto Parra
    Vakhania, Nodari
    Almira, Jose Maria Sigarreta
    Hernandez-Aguilar, Jose Alberto
    ALGORITHMS, 2024, 17 (06)
  • [33] A path cost-based GRASP for minimum independent dominating set problem
    Wang, Yiyuan
    Li, Ruizhi
    Zhou, Yupeng
    Yin, Minghao
    NEURAL COMPUTING & APPLICATIONS, 2017, 28 : S143 - S151
  • [34] Algorithms for minimum m-connected k-dominating set problem
    Shang, Weiping
    Yao, Frances
    Wan, Pengjun
    Hu, Xiaodong
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2007, 4616 : 182 - +
  • [35] 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
  • [36] A path cost-based GRASP for minimum independent dominating set problem
    Yiyuan Wang
    Ruizhi Li
    Yupeng Zhou
    Minghao Yin
    Neural Computing and Applications, 2017, 28 : 143 - 151
  • [37] An Optimization Algorithm for Minimum Connected Dominating Set Problem in Wireless Sensor Network
    Ahn, Namsu
    Park, Sungsoo
    INDUSTRIAL ENGINEERING AND MANAGEMENT SYSTEMS, 2011, 10 (03): : 221 - 231
  • [38] An Efficient Local Search Algorithm for the Minimum k-Dominating Set Problem
    Li, Ruizhi
    Liu, Huan
    Wu, Xiaoli
    Wu, Jun
    Yin, Minghao
    IEEE ACCESS, 2018, 6 : 62062 - 62075
  • [39] Incremental Evaluation Improvements of The RSN Algorithm for the Minimum Connected Dominating Set Problem
    Liu, Ziwen
    Wu, Xinyun
    PROCEEDINGS OF 2020 IEEE 10TH INTERNATIONAL CONFERENCE ON ELECTRONICS INFORMATION AND EMERGENCY COMMUNICATION (ICEIEC 2020), 2020, : 146 - 149
  • [40] An efficient local search algorithm for minimum positive influence dominating set problem
    Sun, Rui
    Wu, Jieyu
    Jin, Chenghou
    Wang, Yiyuan
    Zhou, Wenbo
    Yin, Minghao
    COMPUTERS & OPERATIONS RESEARCH, 2023, 154
12345