2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008

Min-Degree Constrained MST Problem: an evolutionary approach

Authors: A. M. de Almeida, R. Salgueiro, O. Oliveira

Ref.: Proc. of the 5th International Conference on Bioinspired Optimization Methods and their Applications, 121 (2012)

Abstract: This work describes a genetic approach for the combinatorial optimiza- tion problem named the Min-Degree Constrained Minimum Spanning Tree (md-MST). Given a connected, undirected and weighted graph, the md-MST aims to find a minimal spanning tree that obeys an ad- ditional lower bound (d) on the degree of each node of the tree. This problem is NP-hard and thus a suitable target for heuristics. We de- cided to approach the problem via evolutionary algorithms. Two novel genetic algorithms are presented differing in their representations of can- didate trees and the operations that they apply to these chromosomes. While one uses a set of node leaves randomly chosen as chromosome and enforces the construction of a complete spanning tree, the other uses a representation of the set of arcs instead. Both genetic versions perform very favorably when compared with the best results known so far, both in terms of running time as well as in better quality solutions.

URL: bioma.ijs.si