The maximum-leaf spanning tree problem: Formulations and facets
The Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree in a given undirected graph, whose number of leaves (vertices of degree 1) is maximum. In this article, we consider an integer programming approach to the MLSTP. We provide two formulations of the MLSTP and study the facial structure of polytopes arising from the formulations. Moreover, several relaxation problems are compared. (C) 2004 Wiley Periodicals, Inc.
spanning trees facets integer programming valid inequalities