English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/164419
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:


The Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches

AuthorsDavidson, Pedro Pinacho; Blum, Christian ; Lozano, Jose A.
KeywordsGraph theory
Combinatorial optimization
Issue Date20-Apr-2017
CitationEvoCOP 2017: Evolutionary Computation in Combinatorial Optimization LNCS 10197: 201-214 (2017)
AbstractThis work deals with the so-called weighted independent domination problem, which is an NP-hard combinatorial optimization problem in graphs. In contrast to previous theoretical work from the literature, this paper considers the problem from an algorithmic perspective. The first contribution consists in the development of an integer linear programming model and a heuristic that makes use of this model. Second, two greedy heuristics are proposed. Finally, the last contribution is a population-based iterated greedy algorithm that takes profit from the better one of the two developed greedy heuristics. The results of the compared algorithmic approaches show that small problem instances based on random graphs are best solved by an efficient integer linear programming solver such as CPLEX. Larger problem instances are best tackled by the population-based iterated greedy algorithm. The experimental evaluation considers random graphs of different sizes, densities, and ways of generating the node and edge weights. © Springer International Publishing AG 2017.
Identifiersdoi: 10.1007/978-3-319-55453-2_14
issn: 03029743
isbn: 978-3-319-55452-5
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
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.