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 条

[21] 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)
[22] Simulated annealing with stochastic local search for minimum dominating set problem
Hedar, Abdel-Rahman
Ismail, Rashad
INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS, 2012, 3 (02) : 97 - 109
[23] A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem
Lin, Geng
Guan, Jian
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2018, 33 (02) : 305 - 322
[24] The Minimum Weight Dominating Set Problem under Hybrid Uncertain Environments
Wang, Chenyin
Luo, Dongling
Zeng, Mowei
Yi, Yang
Zhou, Xiaocong
ADVANCED DEVELOPMENT IN AUTOMATION, MATERIALS AND MANUFACTURING, 2014, 624 : 545 - 548
[25] A swarm intelligence approach to minimum weight independent dominating set problem
Rasheed, Mohd Danish
Singh, Alok
Mallipeddi, Rammohan
COMPUTERS & ELECTRICAL ENGINEERING, 2025, 123
[26] On the complexity of the minimum outer-connected dominating set problem in graphs
D. Pradhan
Journal of Combinatorial Optimization, 2016, 31 : 1 - 12
[27] MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem
Okumus, Fatih
Karci, Seyda
APPLIED SCIENCES-BASEL, 2024, 14 (20):
[28] On minimum m-connected k-dominating set problem in unit disc graphs
Weiping Shang
Frances Yao
Pengjun Wan
Xiaodong Hu
Journal of Combinatorial Optimization, 2008, 16 : 99 - 106
[29] Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Minimum Connected Dominating Set Problem
Jovanovic, Raka
Tuba, Milan
COMPUTER SCIENCE AND INFORMATION SYSTEMS, 2013, 10 (01) : 133 - 149
[30] A note on the complexity of minimum dominating set
Grandoni, Fabrizio
JOURNAL OF DISCRETE ALGORITHMS, 2006, 4 (02) : 209 - 214

← 1 2 3 4 5 →