At least version of the generalized minimum spanning tree problem

Petrică C. PopAndrei Horvat MarcCorina Pop Sitar



Full PDF


We consider the at least version of the Generalized Minimum Spanning Tree Problem, denoted by L-GMST, which consists in finding a minimum cost tree spanning at least one node from each node set of a complete graph with the nodes partitioned into a given number of node sets. We describe new integer programming formulations of the L-GMST problem and establish relationships between the polytopes corresponding to their linear relaxations.

Additional Information


Horvat-Marc, Andrei, Pop Sitar, Corina, Pop, Petrică Claudiu