Busca avançada
Ano de início
Entree

Limitantes duais e algoritmos exatos para problemas de dilatação mínima em grafos geométricos

Processo: 12/17965-6
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de novembro de 2012
Vigência (Término): 31 de julho de 2014
Á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   Programação linear inteira

Resumo

Este projeto tem por objetivo a produção de uma dissertação a serdesenvolvida no Programa de Mestrado em Ciência da Computação daUNICAMP, cujo tema de pesquisa é o chamado problema da dilataçãomínima em grafos geométricos. Trata-se de um caso particular doprojeto de redes com boa qualidade de conexão e/ou baixo custo, umproblema frequentemente encontrado em situações práticas. Nesteprojeto de pesquisa investiga-se a situação na qual deseja-se obteruma rede que conecte um conjunto dado de pontos no plano de forma aminimizar a dilatação (melhor qualidade) utilizando poucas arestas(baixo custo). Esse problema tem como entrada um conjunto de pontosP={p1,p2, ...,pn} no plano. Define-se, então, o grafo geométrico G(P)associado a P como sendo o grafo não-direcionado, ponderado e completocom n vértices, onde o peso de uma aresta corresponde à distânciaeuclidiana entre os pontos representados por suas extremidades. Oobjetivo é encontrar um subgrafo gerador G de G(P) que minimize amaior razão entre os comprimentos do caminho mais curto em G e em G(P)para todo par de vértice do grafo, medida essa chamada de dilatação deG. Deverão ser analisados os casos em que a rede projetada G seja umgrafo simples conexo com n-1+k arestas, com k maior ou igual a0. Especial atenção é dada para o caso em que k = 0 e G é uma árvoregeradora. A abordagem será através das relaxações lagrangiana elinear e de algoritmos exatos.