Busca avançada
Ano de início
Entree

Algoritmos lagrangeanos para o problema da árvore geradora de dilatação mínima em um grafo geométrico

Processo: 11/07929-0
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de julho de 2011
Vigência (Término): 30 de junho de 2012
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Alex Fernando Brandt
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Geometria computacional   Otimização combinatória   Relaxação Lagrangeana

Resumo

Este projeto de Iniciação Científica tem por objetivo estudar a aplicação da Relaxação Lagrangeana ao Problema da Árvore Geradora de Dilatação Mínima em Grafos Geométricos (PAGDMGG) visando encontrar limitantes primais e duais para o valor ótimo. Esse problema tem como entrada um conjunto de pontos P no plano. Define-se, então, o grafo geométrico G(P) associado a P como sendo o grafo não-direcionado, ponderado e completo com n vértices, onde o peso de uma aresta corresponde à distância euclidiana entre os pontos representados por suas extremidades. O objetivo é encontrar uma árvore geradora T de G(P) que minimize a maior razão entre os comprimentos do caminho mais curto em T e em G(P) para todo par de vértice do grafo, medida essa chamada de dilatação de T. O fato do PAGDMGG ser NP-Difícil justifica o uso de Relaxação Lagrangeana para obtenção de limitantes para o valor ótimo. Esses limitantes podem ser usados na avaliação de outros métodos de solução propostos para o problema como, por exemplo, heurísticas. (AU)