O problema da floresta geradora k-rotulada

Detalhes bibliográficos
Ano de defesa: 2020
Autor(a) principal: Figueredo, Pedro Jorge de Abreu
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/50722
Resumo: In this work, we study the k-Labeled Spanning Forest Problem. Among the problems in edge labeled graphs, this one aims at finding a spanning subgraph that is a forest with the least amount of components and with a positive integer limiting factor k for the number of different labels used. The problem is NP-Hard, as it is a generalization of the Minimal Labeled Spanning Tree Problem, and most of the methods proposed in the literature are based on metaheuristics. We study the characteristics of the problem and relate it to the relevant literature in labeled graphs. Through the studied properties, we establish a class on which the problem is solved in polynomial time. We also explore the characterizations of the problem to propose three mathematical models in 0-1 integer and mixed-integer programming. We propose Branch&Cut methods to solve the problem exactly, using an algorithm to separate Colorful Cuts. Moreover, we propose a parallelization for the only exact method available in the literature, which applies a backtracking procedure. We present preliminary computational experiments with the models and the backtracking method, using test instances suggested by the literature. We apply improvements to the resolution methods by exploring valid inequalities as cuts, branching rules, pruning, and bounds. Besides, we apply Benders decomposition to the proposed flow model. Then, we test the models on graphs with different edge density parameters, still pertinent to the problem. Among these tests, we show the best-found configurations for the models and Cplex.