Algorithms for the minimum weight k-fold (connected) dominating set problem

被引：0

作者：

Wenkai Ma

Deying Li

Zhao Zhang

机构：

[1] Renmin University of China,Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information

[2] Xinjiang University,College of Mathematics and System Sciences

来源：

Journal of Combinatorial Optimization | 2012年 / 23卷

关键词：

-fold dominating set; Slab decomposition; Algorithm; Unit ball graph;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.

引用

页码：528 / 540

页数：12

共 28 条

[21] A greedy algorithm for the connected positive influence dominating set in k-regular graphs
He, Mengmeng
Hou, Bo
Liu, Wen
Wu, Weili
Du, Ding-Zhu
Gao, Suogang
PURE AND APPLIED MATHEMATICS QUARTERLY, 2022, 18 (06) : 2461 - 2478
[22] A Self-Adaptive Variant of CMSA: Application to the Minimum Positive Influence Dominating Set Problem
Anil Akbay, Mehmet
Lopez Serrano, Albert
Blum, Christian
INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2022, 15 (01)
[23] An improved DV-Hop localization with minimum connected dominating set for mobile nodes in wireless sensor networks
Kumar, Gulshan
Rai, Mritunjay Kumar
Saha, Rahul
Kim, Hye-jin
INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS, 2018, 14 (01):
[24] A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
Kamei, Sayaka
Kakugawa, Hirotsugu
THEORETICAL COMPUTER SCIENCE, 2012, 428 : 80 - 90
[25] An O(n+m)-time algorithm for finding a minimum-weight dominating set in a permutation graph
Rhee, C
Liang, YD
Dhall, SK
Lakshmivarahan, S
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) : 404 - 419
[26] Multi-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problem
Nakkala, Mallikarjun Rao
Singh, Alok
Rossi, Andre
APPLIED SOFT COMPUTING, 2021, 108
[27] Cluster head selection based on Minimum Connected Dominating Set and Bi-Partite inspired methodology for energy conservation in WSNs
Priyadarshini, R. Raj
Sivakumar, N.
JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES, 2021, 33 (09) : 1132 - 1144
[28] Solving the 2-connected m-dominating set problem using a GRASP approach for applications in power systems
Jovanovic, Raka
Bayram, Islam Safak
Voss, Stefan
PROCEEDINGS 2018 IEEE 12TH INTERNATIONAL CONFERENCE ON COMPATIBILITY, POWER ELECTRONICS AND POWER ENGINEERING (CPE-POWERENG 2018), 2018,

← 1 2 3 →