| Article ID: | iaor20043732 |
| Country: | Netherlands |
| Volume: | 43 |
| Issue: | 4 |
| Start Page Number: | 212 |
| End Page Number: | 223 |
| Publication Date: | Apr 2004 |
| Journal: | Networks |
| Authors: | Fujie Tetsuya |
| Keywords: | programming: integer |
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.