Formulação matemática para o problema da árvore t-spanner de custo mínimo

• Gabriel H. de Sousa UFC / Grupo de Pesquisa ParGO
• Manoel Campêlo UFC / Grupo de Pesquisa ParGO

DOI: https://doi.org/10.5753/etc.2023.230869

Resumo

O Problema da Árvore t-Spanner de Custo Mínimo, cuja entrada é um grafo simples G, ponderado em arestas, e um parâmetro t ≥ 1, consiste em determinar uma árvore geradora T de G de menor custo dentre aquelas onde a distância entre qualquer par de vértices i e j em T é no máximo t vezes o menor peso de um caminho entre i e j em G. Propomos uma formulação matemática que pode ser derivada pela projeção de uma formulação já existente. Implementamos ambos os modelos e comparamos seus desempenhos computacionais.

Referências

Braga, H. V. V. (2019). Algoritmos exatos para problemas de spanner em grafos. 2019. Tese (Doutorado em Ciência da Computação) Universidade de São Paulo, São Paulo.

Brandstadt, A., Dragan, F. F., Le, H.-O., e Le, V. B. (2004). Tree spanners on chordal graphs: complexity and algorithms. Theor. Comput. Sci., 310(1):329 – 354.

Cai, L. e Coneil, D. G. (1995). Tree spanners. Journal on Discrete Mathematics, 8(3):359 – 387.

Campelo, M. e Sousa, G. H. (2021). An enumerative algorithm for the minimum weight t-spanner tree problem. LIII Simpósio Brasileiro de Pesquisa Operacional, pages 1 – 12.

Campelo, M. e Sousa, G. H. (2022). Nova formulação e desigualdades válidas para o problema da Árvore t-spanner de custo mínimo. LIV Simpósio Brasileiro de Pesquisa Operacional, pages 1 – 12.

Martin, R. K. (1991). Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters, 10:119 – 128.

Singh, K. e Sundar, S. (2018). Artifical bee colony algorithm using problem-specific neighborhood strategies for the tree t-spanner problem. Applied Soft Computing, 62:110 – 118.

Sousa, G. H. (2021). O Problema da árvore t-spanner de Custo Mínimo. 2021. Dissertação (Mestrado em Ciência da Computação), Universidade Federal do Ceará.