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 条
  • [11] Minimum Total Communication Power Connected Dominating Set in Wireless Networks
    Li, Deying
    Kim, Donghyun
    Zhu, Qinghua
    Liu, Lin
    Wu, Weili
    WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2012, 2012, 7405 : 132 - 141
  • [12] Application of CMSA to the Minimum Positive Influence Dominating Set Problem
    Akbay, Mehmet Anil
    Blum, Christian
    ARTIFICIAL INTELLIGENCE RESEARCH AND DEVELOPMENT, 2021, 339 : 17 - 26
  • [13] Minimum Connected Dominating Set Construction in Wireless Networks under the Beeping Model
    Yu, Jiguo
    Jia, Lili
    Yu, Dongxiao
    Li, Guangshun
    Cheng, Xiuzhen
    2015 IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (INFOCOM), 2015,
  • [14] Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
    Chen, Jiejiang
    Cai, Shaowei
    Wang, Yiyuan
    Xu, Wenhao
    Ji, Jia
    Yin, Minghao
    ARTIFICIAL INTELLIGENCE, 2023, 314
  • [15] MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem
    Okumus, Fatih
    Karci, Seyda
    APPLIED SCIENCES-BASEL, 2024, 14 (20):
  • [16] Limitations on Low Variance k-Fold Cross Validation in Learning Set of Rules Inducers
    Vasinek, Michal
    Platos, Jan
    Snasel, Vaclav
    2016 8TH INTERNATIONAL CONFERENCE ON INTELLIGENT NETWORKING AND COLLABORATIVE SYSTEMS (INCOS), 2016, : 207 - 214
  • [17] A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks
    Zhang, Zhao
    Gao, Xiaofeng
    Wu, Weili
    Du, Ding-Zhu
    JOURNAL OF GLOBAL OPTIMIZATION, 2009, 45 (03) : 451 - 458
  • [18] A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks
    Zhao Zhang
    Xiaofeng Gao
    Weili Wu
    Ding-Zhu Du
    Journal of Global Optimization, 2009, 45 : 451 - 458
  • [19] Identification of key nodes and vital edges in aviation network based on minimum connected dominating set
    Li, Jiawei
    Wen, Xiangxi
    Wu, Minggong
    Liu, Fei
    Li, Shuangfeng
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2020, 541
  • [20] Relaxed Connected Dominating Set Problem for Power System Cyber-Physical Security
    Sou, Kin Cheong
    Lu, Jie
    IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, 2022, 9 (04): : 1780 - 1792
123