Novos desenvolvimentos para a solução do problema de partição de um grafo em árvores K-capacitadas

Abstract

The minimum k-capacitated tree partition problema (MkCTP) asks for a partition of a graph into two or more trees, in a way that each component spans a minimum number of vertices, whose sum of the edge weights is smallest possible. In this work, we briefly review some heuristics for solving the MkCTP. Among these, we give emphasis to a Branch-and-Bound algorithm and propose some improvements on it. We propose two novel heuristics for MkCTP that seek to create trees that have approximately the same cardinality. We evaluate, from a computational point of view, the branch-and-bound algorithm, as well as the proposed improvements. Our computational experiments show the efficiency of some of the proposed improvements to this method, since it has the best costs in the objective function (bounds) and the smallest running times when compared to the algorithms available in the literature and the heuristics proposed in this work.