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
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

Page view(s)

checked on Feb 6, 2023

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.