Um Algoritmo Branch-and-Cut para o Problema de
Steiner com Grupos
Fernando Mario de Oliveira Filho
Orientador: Prof. Dr. Carlos Eduardo Ferreira
Supervisora: Profa. Dra. Yoshiko Wakabayashi
Projeto baseado na Iniciação Científica
Resumo
Neste trabalho abordamos o problema de Steiner com grupos, que
consiste em dado um grafo com custos nas arestas e uma coleção de
subconjuntos do conjunto de vértices, encontrar um subgrafo que
conecte pelo menos um vértice de cada conjunto da coleção e que tenha
custo mínimo. O problema é uma generalização do problema de Steiner em
grafos e surge naturalmente no desenvolvimento de circuitos
VLSI. Apresentamos estudos feitos para o desenvolvimento de um
algoritmo seguindo a estratégia branch-and-cut para o
problema. O trabalho se baseia num projeto de iniciação científica que
teve apoio da FAPESP e que foi desenvolvido desde Agosto de 2001 até
Agosto de 2003.
Apontadores
Você pode acessar a proposta de projeto
entregue durante o ano ou acessar a página da monografia entregue durante a
disciplina.
Fernando Mario de Oliveira Filho
<fmario@linux.ime.usp.br>
Segunda, 6 de Dezembro 2003