Generalized spanning trees

In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.