Estratégias de resolução exata para o problema do corte global rotulado mínimo

Abstract

In this work, we approach the Minimum Labeling Global Cut Problem (MLGCP), which is a combinatorial analysis problem and can be formally defined as: Let G = (V, E, L) be an edge-labeled graph in which V is the set of vertices of G, E is the set of edges, L is the set of labels (colors) on E and each edge e ∈ E has a label L(e) associated; The goal of MLGCP is to find a subset L 0 ⊆ L of labels such that G = (V, E0 , L\L 0 ) is not connected and |L 0 | is minimized. So, in order to solve this problem, we developed some strategies for exact resolution, extended and adapted the concept of chromatic closure, and developed a new family of mathematical formulations called MFd. For the construction of the MFd, we were based on a model present in literature called PART2, defined in Silva et al (2016). The computational experiments demonstrated that the model proposed in this work obtained a great improvement of time compared to the PART2 model.