HEURÍSTICAS E MODELO MATEMÁTICO PARA O PROBLEMA DE T-SPANNER EM GRAFOS

Abstract

Dados um grafo G, definido pelo par (V, E) de vértices e arestas, com uma ponderação das arestas, bem como um escalar positivo t, um subgrafo H de G é dito um t-spanner quando ele é gerador, conexo e, para todos u, v ∈ V, a distância entre u e v em H é no máximo t vezes a distância entre u e v em G. O problema de encontrar um t-spanner de peso mínimo tem conexões com outros problemas clássicos em grafos, como o da Árvore Geradora Mínima e o de Caminhos Mínimos, e também aplicações diversas, como em computação distribuída e em redes de computadores. No presente trabalho, propuseram-se heurísticas para o problema, a maioria baseadas em procedimentos gulosos, além de um modelo de programação inteira com um número de variáveis da ordem de O(n⁴), onde n é o número de vértices do grafo. A resolução do modelo foi realizada pela ferramenta de otimização Gurobi, na linguagem de programação C++, que também foi utilizada para a implementação das heurísticas. Em testes computacionais com grafos com características parametrizadas, comparou-se a qualidade das soluções, bem como o tempo de obtenção destas. O tempo demandado pelas heurísticas foi ordens de magnitude menor do que aquele para encontrar a solução exata, o que motivou o fornecimento de valores iniciais calculados por um pré-processamento via heurísticas para o modelo, visando uma resolução via ramificações (branch and bound and cut), o que acelerou o processo. O início do projeto foi baseado em uma revisão bibliográfica sobre o tema, seguido de propostas de algoritmos e, por fim, testes computacionais, o que garantiu uma base sólida tanto teórica quanto experimental. Este trabalho foi realizado com apoio financeiro do CNPQ em colaboração com a UFC.