Efficient algorithms for the Generalized Minimum Spanning Tree Problem

We consider a generalization of the classical minimum spanning tree problem called the generalized minimum spanning tree problem and denoted by GMST problem. It is known that the GMST problem belongs to the hard core of NP-hard problems. The aim of this paper is to present an exact exponential time algorithm for the GMST problem as well three efficient algorithms, two of them based on Prim’s and Kruskal’s algorithms for the minimum spanning tree problem and one based on the local global approach. These three algorithms are implemented and computational results are reported for many instances of the problem.