O problema do subgrafo biconexo mínimo generalizado: algoritmos e formulações

• Ano de defesa: 2012
• Autor(a) principal: Rafael Santos Coelho
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: Algoritmos branch-and-cut; Projeto de redes resilientes; Biconexidade em teoria de grafos; Computação
• Link de acesso: http://hdl.handle.net/1843/ESBF-8SUMR5

Given an integer number k > 2 and an undirected simple graph G = (V; E) with positive real weights assigned to its edges, where V is partitioned into k subsets (or clusters), the Generalized Minimum Biconnected Subgraph Problem (GMBSP) amounts to nding a minimum-cost biconnected subgraph S of G, such that S contains exactly one vertex from every cluster of G. In this work, we propose an exact Branch-and-cut algorithm and some heuristics to solve PSBMG. Our Branch-and-cut algorithm separates four classes of valid inequalities for GMBSP, all of them adapted from valid inequalities for other problems related to GMBSP. In order to better assess our solution approaches, we conducted several computational experiments using dense and sparse benchmark instances. For a considerable fraction of those instances, we were able to provide new optimality certicates, as well as better upper and lower bounds.