Authors: | da Silva, Thiago Gouveia de Sousa Filho, Gilberto Barbosa, Igor Mladenović, Nenad Cabral, Lucidio Ochi, Luiz Satoru Aloise, Daniel |
Title: | Efficient heuristics for the minimum labeling global cut problem | Journal: | Electronic Notes in Discrete Mathematics | Volume: | 66 | First page: | 23 | Last page: | 30 | Issue Date: | 1-Apr-2018 | ISSN: | 1571-0653 | DOI: | 10.1016/j.endm.2018.03.004 | Abstract: | Let G=(V,E,L) be an edge-labeled graph. Let V be the set of vertices of G, E the set of edges, L the set of labels (colors) such that each edge e∈E has an associated label L(e). The goal of the minimum labeling global cut problem (MLGCP) is to find a subset L′⊆L of labels such that G′=(V,E′,L\L′) is not connected and |L′| is minimized. In this work, we generate random instances for the MLGCP to perform empirical tests. Also propose a set of heuristics using concepts of Genetic Algorithm and metaheuristic VNS, including some of their procedures, like two local search moves, and an auxiliary data structure to speed up the local search. Computational experiments show that the metaheuristic VNS outperforms other methods with respect to solution quality. |
Keywords: | Connectivity | Edge-Labeled Graphs | Variable Neighborhood Search | Publisher: | Elsevier |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.