Solving the minimum labeling global cut problem by mathematical programming

Let G = (V, E, L) be an edge-labeled graph such that V is the set of vertices, E is the set of edges, L is the set of labels (colors) and each edge e \in E has a label l(e) associated; The goal of the minimum labeling global cut problem (MLGCP) is to find a subset L \subseteq L of labels such that G...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-03
Main Authors: Thiago Gouveia da Silva, Gilberto F de Sousa Filho, Luiz Satoru Ochi, Michelon, Philippe, Gueye, Serigne, Cabral, Lucidio A F
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Formulations
Graph coloring
Graph theory
Labeling
Labels
Mathematical analysis
Mathematical programming
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G = (V, E, L) be an edge-labeled graph such that V is the set of vertices, E is the set of edges, L is the set of labels (colors) and each edge e \in E has a label l(e) associated; The goal of the minimum labeling global cut problem (MLGCP) is to find a subset L \subseteq L of labels such that G = (V, E , L\L ) is not connected and |L| is minimized. This work proposes three new mathematical formulations for the MLGCP as well as branch-and-cut algorithms to solve them. The computational experiments showed that the proposed methods are able to solve small to average sized instances in a reasonable amount of time.
ISSN:2331-8422