English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/197414
Share/Impact:
Statistics
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Title

An algorithm based on ant colony optimization for the minimum connected dominating set problem

AuthorsBouamama, Salim; Blum, Christian ; Fages, Jean-Guillaume
KeywordsMinimum connected dominating set
Ant colony optimization
Reduced variable neighborhood search
Issue DateJul-2019
PublisherElsevier
CitationApplied Soft Computing 80: 672-686 (2019)
AbstractAnt 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.
Publisher version (URL)http://dx.doi.org/10.1016/j.asoc.2019.04.028
URIhttp://hdl.handle.net/10261/197414
DOI10.1016/j.asoc.2019.04.028
ISSN1568-4946
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,35 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.