Busca avançada
Ano de início
Entree

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)