A line graph reformulation for the rainbow spanning forest problem
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Reformulação do gráfico de linhas para o problema da floresta que abrange o arco-íris
Primeiro orientador
Membros da banca
Alexandre Salles da Cunha
Abílio Pereira de Lucena Filho
Geraldo Robson Mateus
Yuri Abitbol de Menezes Frota
Abílio Pereira de Lucena Filho
Geraldo Robson Mateus
Yuri Abitbol de Menezes Frota
Resumo
Let G(V, E) be a connected and undirected graph, with sets of vertices V and edges E, and let L = {L1, L2, ..., Lh} be a finite set of colors. Each edge e ∈ E is colored with a color l ∈ L. A spanning forest F(V, EF ) ⊂ G is a rainbow spanning forest if no connected component in F contains two edges of the same color. The Rainbow Spanning Forest Problem then consists of finding a rainbow spanning forest of G with the minimum number of connected components. In this work, we propose an Integer Programming formulation based on line graphs for the problem, as well as valid inequalities in order to achieve better bounds. We also present a Branch-and-cut algorithm to solve the proposed formulation. Our experiments show that this new formulation yields tighter bounds than other formulations in the literature.
Abstract
Seja G(V, E) um grafo conexo e não direcionado, composto pelo conjunto de vértices V e de arestas E, e seja L = {L1, L2, ..., Lh} um conjunto finito de cores. A cada aresta e ∈ E é associada uma cor l ∈ L. Uma floresta geradora F(V, EF ) ⊂ G é dita iridescente se cada componente conexa em F é composta por arestas de cores diferentes. O problema da Floresta Geradora Iridescente consiste então em encontrar uma floresta geradora iridescente para G com o mínimo número de componentes conexas. Neste trabalho, propomos uma formulação de Programação Inteira baseada em grafos linha para o problema, além de desigualdades válidas com o propósito de gerar limites duais mais fortes. Implementamos então um algoritmo Branch-and-cut para resolver a formulação proposta. Experimentos mostram que a formulação proposta apresenta limites duais significativamente melhores que as formulações encontradas na literatura.
Assunto
Computação - Teses, Otimização combinatória – Teses, Programação inteira - Teses, Floresta Aleatória – Teses, Árvores (Teoria dos grafos) - Teses
Palavras-chave
Line Graphs, Branch-and-Cut