Solving the minimum labeling global cut problem by mathematical programming

An edge‐labeled graph (ELG) is a graph such that is the set of vertices, is the set of edges, is the set of labels (colors), and each edge has a label associated. Given an ELG , the goal of the minimum labeling global cut problem (MLGCP) is to find a subset such that the removal of all edges with la...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2024-11
Main Authors: Koehler, Victor J. de Sousa, Gouveia, Thiago, Sousa Filho, Gilberto Farias de, Ochi, Luiz Satoru, Michelon, Philippe, Gueye, Serigne, Cabral, Lucidio A. F.
Format: Article
Language:English
Subjects:
Computer Science
Operations Research
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An edge‐labeled graph (ELG) is a graph such that is the set of vertices, is the set of edges, is the set of labels (colors), and each edge has a label associated. Given an ELG , the goal of the minimum labeling global cut problem (MLGCP) is to find a subset such that the removal of all edges with labels in disconnects and is minimum. This work proposes three new mathematical formulations for the MLGCP, namely PART , VC , and TE as well as branch‐and‐cut algorithms to solve them. Additionally, a theoretical study was carried out on the MLGCP input graph, leading to the concept of chromatic closure, used in preprocessing algorithms for this model PART . Finally, a comprehensive polyhedral investigation of the model is performed. The computational experiments showed that the model, adopting the chromatic closure concept and its branch‐and‐cut algorithm, can solve small to average‐sized instances in reasonable times.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.13571