A unified greedy approximation for several dominating set problems

被引：2

作者：

Zhong, Hao ^{[1
,3
]}

Tang, Yong ^{[1
,3
]}

Zhang, Qi ^{[2
]}

Lin, Ronghua ^{[1
,3
]}

Li, Weisheng ^{[1
,3
]}

机构：

[1] South China Normal Univ, Sch Comp Sci, Guangzhou 510631, Peoples R China

[2] Guangzhou Coll Commerce, Sch Informat Technol & Engn, Guangzhou 511363, Peoples R China

[3] Pazhou Lab, Guangzhou 510330, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2023年 / 973卷

基金：

中国国家自然科学基金;

关键词：

Dominating set; Connected dominating set; Submodularity; Approximation algorithm; ALGORITHM;

D O I：

10.1016/j.tcs.2023.114069

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Minimum Dominating Set and Minimum Connected Dominating Set are classic graph problems that have been studied extensively in the literature. These two problems and their various variants are NP-hard in a general graph, and for some of them greedy approximation algorithms have been proposed. In this paper, by designing two potential functions that enjoy submodularity or a weak submodularity, we propose a unified O(ln & delta;)-approximation algorithm for a generalized Minimum (Connected) Dominating Set that includes Minimum (Connected) Dominating Set, Minimum (Connected) Total Dominating Set, Minimum (Connected) *-Dominating Set and Minimum (Connected) Positive Influence Dominating Set, where & delta; is the maximum node degree of the input graph. For each specific version of the generalized Minimum (Connected) Dominating Set, the unified algorithm either matches the best one of existing approximation algorithms, or gives the first approximation solution.& COPY; 2023 Elsevier B.V. All rights reserved.

引用

页数：8

共 22 条

[1]

[Anonymous], 2010, Proceedings of the 23rd International Conference on Computational Linguistics

[2] A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks [J].

Chen, Weidong ;

Zhong, Hao ;

Wu, Lidong ;

Du, Ding-Zhu .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (01) :1-20

[3] Time-Bounded Essential Localization for Wireless Sensor Networks [J].

Cheng, Wei ;

Zhang, Nan ;

Cheng, Xiuzhen ;

Song, Min ;

Chen, Dechang .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2013, 21 (02) :400-412

[4] Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET [J].

Chinnasamy, A. ;

Sivakumar, B. ;

Selvakumari, P. ;

Suresh, A. .

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS, 2019, 22 (Suppl 5) :12795-12804

[5]

Du DZ, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P167

[6] Identify Connected Positive Influence Dominating Set in Social Networks Using Two-Hop Coverage [J].

Du, Hongwei ;

Yuan, Caiwei ;

Yuan, He ;

Wei, Shanshan ;

Xu, Wen .

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS, 2019, 6 (05) :956-967

[7]

Geng Lin, 2020, Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery. Advances in Intelligent Systems and Computing (AISC 1074), P506, DOI 10.1007/978-3-030-32456-8_55

[8]

Guangyuan Wang, 2011, Advances in Web-Based Learning - ICWL 2011. Proceedings 10th International Conference, P82, DOI 10.1007/978-3-642-25813-8_9

[9] Influence Spread in Social Networks with both Positive and Negative Influences [J].

He, Jing ;

Xie, Ying ;

Du, Tianyu ;

Ji, Shouling ;

Li, Zhao .

COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 :615-629

[10] Minimum-sized Influential Node Set Selection for Social Networks under the Independent Cascade Model [J].

He, Jing ;

Ji, Shouling ;

Beyah, Raheem ;

Cai, Zhipeng .

MOBIHOC'14: PROCEEDINGS OF THE 15TH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING, 2014, :93-102

← 1 2 3 →