Arredondamento probabilístico para o problema de AGM com restrição de grau e centrais e terminais fixos

Abstract

A tree is a particular type of graph that holds great importance in the field of Optimization and Combinatorics. Such importance is justified because it is a framework used to model numerous problems or subproblems involving connectivity. A graph can have many spanning trees, i.e a tree that contains all its vertices of this graph. If each edge of the graph has a cost, we have that the cost of the spanning tree will be the sum of the costs of its edges. So if the edges have different costs, then in the worst case, each possible tree will have a different cost. The problem is to find the minimum-weight spanning tree. This problem is known as Minimum-Weight Spanning Tree (MST). In the literature, there are several variations of the MST, where additional restrictions are imposed. In particular, the present study emphasizes the MST problem with minimum restriction. We focus on the Min-Degree Constrained Minimum Spanning Tree problem with Fixed Centrals and Terminals (MDF-MST) (DIAS et al., 2017). This work aims to propose and evaluate a new solution to the MDF-MST problem, comparing the results with models in Integer Linear Programming existent in the literature. By means of computational tests the cost was analyzed in terms of time and quality of the solution. At the end, two solution approaches were compared: i) Integer Linear Programming (PLI) and ii) Randomized Rounding Approach (AP). We conclude that the proposed heuristic using the randomized rounding approach presented the best results in terms of solution time.