Eduardo Uchoa
Depto de Engenharia de Produção
Universidade Federal Fluminense
Sexta-feira, 30 de agosto de 2002, às 14:30 horas
Sala 268, Bloco A, IME-USP
Resumo:
O Problema de Steiner em Grafos (PSG) consiste em conectar um subconjunto de vértices de um grafo usando um subconjunto de arestas de custo total mínimo. O PSG é um clássico problema NP-difícil, intensamente estudado devido à suas numerosas aplicações. Essa palestra é um "survey" dos grandes avanços ocorridos nos últimos 4 anos nos algoritmos para esse problema, avanços que atualmente permitem que instâncias reais da ordem de 100.000 arestas possam ser resolvidas de forma exata. Destaca-se as várias contribuições feitas por um grupo de pesquisadores da PUC-Rio. Os diversos algoritmos desenvolvidos estão integrados em um complexo pacote computacional (25.000 linhas de código C++) chamado BOSSA, disponível para uso acadêmico e já usado por vários outros pesquisadores no mundo.