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

Abstract

The Minimum Weight t-Spanner Tree Problem, whose input is an edge-weighted simple graph G and a parameter t ≥ 1, consists in determining a spanning tree T of G of minimum weight among those where the path between each pair of vertices i and j in T has weight at most t times the minimum weight of a path between i and j in G. We propose a mathematical formulation which can be derived from a projection of an existing formulation. We implemented both models and compared their computational performance.

References

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á.