Generalized Minimum Spanning Tree Polytope and Related Polytopes

摘要

The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls foerent version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.