Uma análise de métodos de separação de grafos quando aplicados ao problema da árvore t-spanner de peso mínimo

Abstract

The minimum 𝑡-spanner tree problem consists of finding a spanning tree where the distances between any pair or vertices are at most 𝑡 times that of the original graph. After that, one searches for a solution where the sum of edge weights is minimized. This problem has many uses when it comes to computer networks due to its property of creating concise but efficient graph structures. Nevertheless, even when using techniques like integer linear programming, the execution time for large instances diminishes its use in a practical sense. In this context, techniques such as the separation by articulation points, that involves separating different blocks of the grapph, determined by its articulation points, and after finding the answer for each block, they are combined to find the proper solution. This technique has not been properly tested and can result in the gain of performance when searching for an optimal solution for the problem. By virtue of this fact, it is deemed necessary to properly test this possibility. Furthermore, taking into consideration the cases where articulation points do not exist, tests are made with a similar technique for chordal graphs, based on balanced clique separators. Analysis of the experiments indicated that decomposition by articulation points contributed to a reduction of approximately 80% in execution time on average, in contrast to the approach based on the balanced clique separator, which resulted in a worsening of execution time.