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

• Processo: 12/17965-6
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de novembro de 2012
• Data de Término da vigência: 31 de julho de 2014
• Área de 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
• Palavra(s)-Chave do Pesquisador: Algoritmos Exatos | Dilatação Mínima | Geometria Computacional | Otimização Combinatória | programação linear inteira | Relaxação Lagrangiana | Otimização Combinatória

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.

Publicações acadêmicas

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

BRANDT, Alex Fernando. Algoritmos exatos para problemas de dilatação mínima em grafos geométricos. 2014. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.