Algoritmos de aproximacao para o problema da arvore de steiner.

• Processo: 06/54375-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2006
• Data de Término da vigência: 31 de dezembro de 2007
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: Mário César San Felice
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Arvore De Steiner | Implementacao De Algoritmos | Otimizacao Combinatoria

Resumo

O problema da árvore de Steiner é um problema clássico em otimização combinatória. Ele aparece dentro do contexto de projetos de circuitos VLSI, árvores filogenéticas e redes. O objetivo deste projeto é estudar e implementar vários algoritmos de aproximação para o problema da árvore de Steiner. Esperamos que ao final do projeto o aluno tenha adquirido familiaridade com as técnicas usadas no projeto dos algoritmos e com os aspectos de implementação eficiente de algoritmos combinatórios. (AU)