.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Minimum connected dominating set
Ant colony optimization
Reduced variable neighborhood search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.6
论文数:
1.4W
被引数:
4.8W
机构
引用论文
Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks
PREAI
分享收藏Optimised Anaesthesia to Reduce Post Operative Cognitive Decline (POCD) in Older Patients Undergoing Elective Surgery, a Randomised Controlled Trial.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAI分享收藏
查看更多内容