Carlos Eduardo Ferreira
IME-USP
Sexta-feira, 15 de março de 2002, 15:00
Sala 267, Bloco A, IME-USP
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.