.png){kind=icon}
.png){kind=icon}
Return
An algorithm based on ant colony optimization for the minimum connected dominating set problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2019.04.028.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality. (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Minimum connected dominating set
Ant colony optimization
Reduced variable neighborhood search
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W
View more organizations