O Problema de Steiner com Grupos

                       Carlos Eduardo Ferreira 
                              IME-USP


                 Quarta-feira, 15 de dezembro de 2004 <------ Atenção
                        Sala 85 (IC2), 14:00hs <------ Atenção


Resumo: 

Dado um grafo $G=(V,E)$, uma coleção $\cal R$ de subconjuntos de $V$,
e uma função $c_e : E \longrightarrow Q_+$, encontrar um subgrafo
conexo $T$ de $G$ de custo mínimo que contenha pelo menos um vértice
de cada $R \in \cal R$. Este problema surge naturalmente em uma
aplicação de planejamento de circuitos VLSI na fase de
roteamento. Vamos mostrar alguns resultados da literatura para o
problema, e alguns novos resultados que obtivemos sobre novas técnicas
de redução e alguns resultados sobre poliedros associados ao
problema. Este trabalho está em andamento e é conjunto com Fernando
Mario de Oliveira Filho.