O Problema de Steiner em Grupos

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.