Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set

作     者：Zhang, Xindi Li, Bohan Cai, Shaowei Wang, Yiyuan 

作者机构：State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China School of Computer Science and Technology University of Chinese Academy of Sciences Beijing China School of Computer Science and Information Technology Northeast Normal University China Key Laboratory of Applied Statistics of MOE Northeast Normal University China 

出 版 物：《Journal of Artificial Intelligence Research》 (J Artif Intell Res)

年 卷 期：2021年第71卷

页      面：89-119页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Shaowei Cai and Yiyuan Wang are corresponding authors. We would like to thank the anonymous referees for their helpful comments. This work was supported by Beijing Academy of Artificial Intelligence (BAAI)  Youth Innovation Promotion Association  Chinese Academy of Sciences [No. 2017150]  NSFC Grant 61806050  and the Fundamental Research Funds for the Central Universities 2412020FZ030 

主　　题：Local search (optimization) 

摘      要：The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Most previous works focused on solving MCDS problem in graphs with relatively small size, mainly due to the complexity of maintaining connectivity. This paper explores techniques for solving MCDS problem in massive real-world graphs with wide practical importance. Firstly, we propose a local greedy construction method with reasoning rule called 1hopReason. Secondly and most importantly, a hybrid dynamic connectivity maintenance method (HDC+) is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Thirdly, we adopt a two-level vertex selection heuristic with a newly proposed scoring function called chrono-safety to make the algorithm more considerate when selecting vertices. We design a new local search algorithm called FastCDS based on the three ideas. Experiments show that FastCDS significantly outperforms five state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks. © 2021 AI Access Foundation. All rights reserved.