| Processo: | 95/08929-9 |
| Linha de fomento: | Bolsas no Brasil - Mestrado |
| Vigência (Início): | 01 de março de 1996 |
| Vigência (Término): | 30 de abril de 1997 |
| Área do conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação |
| Pesquisador responsável: | Cid Carvalho de Souza |
| Beneficiário: | Aminadab Pereira Nunes |
| Instituição-sede: | Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Assunto(s): | Otimização combinatória Combinatória poliédrica Geometria computacional Programação linear inteira Triangulação (geometria) |
Resumo Este projeto trata do problema da triangulação de custo mínimo (PTCM). Apesar de ser um problema clássico em geometria computacional, o PTCM permanece com sua complexidade desconhecida. Usualmente este problema é resolvido de forma aproximada. Discutiremos neste projeto a possibilidade de resolução exata deste problema utilizando técnicas de programação linear inteira, em particular, através de algoritmos de Branch-AMD-CUT. Além disso, mostramos uma certa equivalência entre o PTCM e o problema do conjunto independente, e comentamos como esta equivalência pode ser útil a este projeto. (AU) | |