carpathian_2006_22_129_135_001

At least version of the generalized minimum spanning tree problem


Petrică C. PopAndrei Horvat MarcCorina Pop Sitar


Abstract

carpathian_2006_22_129_135_abstract

Full PDF

carpathian_2006_22_129_135

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

Author(s)

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