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

• Ano de defesa: 2020
• Autor(a) principal: Medeiros, Jose Fagner Rodrigues
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal da Paraíba; Brasil; Informática; Programa de Pós-Graduação em Informática; UFPB
• Palavras-chave em Português: Grafos com arestas rotuladas; Branch-and-cut; Conectividade; Edge-labeled graphs; Connectivity; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufpb.br/jspui/handle/123456789/18537

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.