NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set
Abstract
The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Despite its practical importance, there are few works on solving MCDS for massive graphs, mainly due to the complexity of maintaining connectivity. In this paper, we propose two novel ideas, and develop a new local search algorithm for MCDS called NuCDS. First, a hybrid dynamic connectivity maintenance method is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Second, we define a new vertex property called \emph{safety} to make the algorithm more considerate when selecting vertices. Experiments show that NuCDS significantly outperforms the state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.
Cite
Text
Li et al. "NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/209Markdown
[Li et al. "NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/li2020ijcai-nucds/) doi:10.24963/IJCAI.2020/209BibTeX
@inproceedings{li2020ijcai-nucds,
title = {{NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set}},
author = {Li, Bohan and Zhang, Xindi and Cai, Shaowei and Lin, Jinkun and Wang, Yiyuan and Blum, Christian},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1503-1510},
doi = {10.24963/IJCAI.2020/209},
url = {https://mlanthology.org/ijcai/2020/li2020ijcai-nucds/}
}