Heurísticas para o problema da árvore de custo mínimo com k-arestas

Abstract

The problem of minimum cost tree with k edges consists in finding for a connected graph and not cost-oriented with the vertices and edges a minimum cost component that is a tree with exactly k edges. We present the mathematical formulation proposed by Fischetti et al. (1994) developed five heuristics, based on the Prim algorithm (1957) and Kruskal (1956) and Dijkstra (1959). One of the heuristics presented in this paper, was competitive, getting very close to the solutions found by the Lagrangian heuristic set bb proposed by Blum and Blesa (2005). The results of our heuristics were compared with those obtained from the heuristic Lagrangian Quintão et al. (2008) e (2010) for the instances of the set g proposed by Blesa and Xhafa (2000) and set bb proposed by Blum and Blesa (2005). The heuristics were developed for version k-ACM-CA. Comparing the results, we analyze the heuristics presented in this paper presents the runtime for each instance, the top two sets compared with those obtained in the Lagrangian Heuristic Quintão et al. (2008) e (2010).The execution times of the heuristic can be improved by leveraging Union-Find, instead of using the depth-first search in addition the edges may be collapsed so that the Dijkstra (1959) is implemented in the collapsed graph.