IJCAI 2020poster0 citations
Two-goal Local Search and Inference Rules for Minimum Dominating Set
Shaowei Cai, Wenying Hou, Yiyuan Wang, Chuan Luo, Qingwei Lin
Abstract
Minimum dominating set (MinDS) is a canonical NP-hard combinatorial optimization problem with applications. For large and hard instances one must resort to heuristic approaches to obtain good solutions within reasonable time. This paper develops an efficient local search algorithm for MinDS, which has two main ideas. The first one is a novel local search framework, while the second is a construction procedure with inference rules. Our algorithm named FastDS is evaluated on 4 standard benchmarks and 3 massive graphs benchmarks. FastDS obtains the best performance for almost all benchmarks, and obtains better solutions than state-of-the-art algorithms on massive graphs.
Heuristic Search and Game Playing: Combinatorial Search and OptimisationHeuristic Search and Game Playing: Heuristic Search
BibTeX
@inproceedings{ijcai2020p204,
title = {Two-goal Local Search and Inference Rules for Minimum Dominating Set},
author = {Cai, Shaowei and Hou, Wenying and Wang, Yiyuan and Luo, Chuan and Lin, Qingwei},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {1467--1473},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/204},
url = {https://doi.org/10.24963/ijcai.2020/204},
}