Resolução exata do problema de partição retangular de um retângulo com pontos no interior:uma abordagem utilizando combinatória polie drica

• Processo: 96/00945-8
• Linha de fomento: Bolsas no Brasil - Mestrado
• Vigência (Início): 01 de maio 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: Cláudio Nogueira de Meneses
• 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): Geometria computacional Combinatória poliédrica Programação linear inteira

Resumo

Dado um conjunto P de N pontos do plano no interior de um retângulo R, estudamos o problema de particionar R em retângulos, introduzindo um conjunto de segmentos de reta de comprimento total mínimo. Em uma partição válida, cada ponto em P precisa ser incluído em no mínimo um dos segmentos de reta introduzidos. Este problema denotado por RG-P tem aplicações em projeto de circuitos VLSI_E E_NP-HARD. Este projeto fundamenta-se no desenvolvimento de um algoritmo exato para o RG-P baseado em técnicas de prog. linear inteira e combinatória poliédrica. Também será feito um estudo computacional comparativo dos algoritmos aproximados para o RG-P na literatura. (AU)