Resolucao exata do problema de particao retangular de um retangulo com pontos no interior:uma abordagem utilizando combinatoria polie drica.

• Processo: 96/00945-8
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de maio de 1996
• Data de Término da vigência: 30 de abril de 1997
• Área de 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
• Palavra(s)-Chave do Pesquisador: Algoritmos Aproximados | Combinatoria Poliedrica | Geometria Computacional | Programacao 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)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

MENESES, Cláudio Nogueira de. Partição retangular minima de um retangulo em programação linear inteira. 1997. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.