Min-Degree Constrained MST Problem: an evolutionary approach

Authors

Abstract

This work describes a genetic approach for the combinatorial optimization 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 additional
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 decided to approach the problem via evolutionary algorithms. Two novel genetic algorithms are presented differing in their representations of candidate
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.

Keywords

Combinatorial optimization, Degree constrained spanning tree, Evolutionary approach, Genetic algorithms, Heuristics

Subject

Genetic Algorithms; Min-Degree Constrained MST Problem

Conference

International Conference on Bioinspired Optimization Methods and their Applications, May 2012