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 条
  • [41] Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
    Gaspers, Serge
    Kratsch, Dieter
    Liedloff, Mathieu
    Todinca, Ioan
    ACM TRANSACTIONS ON ALGORITHMS, 2009, 6 (01)
  • [42] Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks
    Hedar, Abdel-Rahman
    Abdulaziz, Shada N.
    Sewisy, Adel A.
    El-Sayed, Gamal A.
    ALGORITHMS, 2020, 13 (02)
  • [43] The Constant Inapproximability of the Parameterized Dominating Set Problem
    Chen, Yijia
    Lin, Bingkai
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 505 - 514
  • [44] An Approximation Algorithm for a Variant of Dominating Set Problem
    Wang, Limin
    Wang, Wenqi
    AXIOMS, 2023, 12 (06)
  • [45] THE CONSTANT INAPPROXIMABILITY OF THE PARAMETERIZED DOMINATING SET PROBLEM
    Chen, Yijia
    Lin, Bingkai
    SIAM JOURNAL ON COMPUTING, 2019, 48 (02) : 513 - 533
  • [46] Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem
    Cornejo Acosta, Jose Alejandro
    Garcia Diaz, Jesus
    Menchaca-Mendez, Ricardo
    Menchaca-Mendez, Rolando
    MATHEMATICS, 2020, 8 (09)
  • [47] A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
    Zhu, Xu
    Wang, Wei
    Shan, Shan
    Wang, Zhong
    Wu, Weili
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 23 (04) : 443 - 450
  • [48] A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
    Xu Zhu
    Wei Wang
    Shan Shan
    Zhong Wang
    Weili Wu
    Journal of Combinatorial Optimization, 2012, 23 : 443 - 450
  • [49] An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem
    PAN Shiwei
    MA Yiming
    WANG Yiyuan
    ZHOU Zhiguo
    JI Jinchao
    YIN Minghao
    HU Shuli
    Frontiers of Computer Science, 2023, 17 (04)
  • [50] Algorithms for minimum m-connected k-tuple dominating set problem
    Shang, Weiping
    Wan, Pengjun
    Yao, Frances
    Hu, Xiaodong
    THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) : 241 - 247
12345