Empacotamentos de árvores de Steiner

                       Carlos Eduardo Ferreira 
                              IME-USP


                   Sexta-feira, 3 de maio
                      sala:     IC1-01    <------ Atencao
                      horario:  10:00hs   <------ Atencao


Resumo: 

Neste seminário mostramos alguns problemas de Otimização Combinatória 
que surgem no projeto de circuitos eletrônicos. Em especial, 
mostramos que o projeto de roteamento global e detalhado destes 
circuitos pode ser modelado como um problema de empacotamento de 
árvores de Steiner em certos grafos planares. 

Para um caso especial deste problema (conhecido como "channel routing")
o grafo onde o roteamento ocorre é uma grade e os terminais a serem 
conectados estão todos na borda inferior ou superior desta grade. Neste 
caso, o interesse é minimizar a largura da rede de tal forma que o 
problema continue viável. Mostramos condições necessárias para a 
existência do roteamento.