Title: The Generalized Minimum Spanning Tree Problem

Given a graph G=(V,E) with the nodes partitioned into clusters and edges defined between nodes from different clusters, the GMSTP is to find a minimum tree spanning a subset of nodes which includes exactly one node from every cluster. The GMSTP is an NP-hard problem. We present several formulations of the problem and compare the polyhedra associated to the corresponding LP-relaxations. We present also an approximation algorithm for the GMSTP in the case that the cost function associated to the edges is non-negative and satisfies the triangle inequality and the clusters have bounded size.