The maximum‐leaf spanning tree problem: Formulations and facets
Author:
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- An exact algorithm for the maximum leaf spanning tree problemComputers & Operations Research, 2003
- Approximating Maximum Leaf Spanning Trees in Almost Linear TimeJournal of Algorithms, 1998
- 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves1998
- Minimal spanning trees with a constraint on the number of leavesEuropean Journal of Operational Research, 1998
- Approximation algorithms for connected dominating sets1996
- A short note on the approximability of the maximum leaves spanning tree problemInformation Processing Letters, 1994
- Integer and Combinatorial Optimization1988
- Constructing full spanning trees for cubic graphsInformation Processing Letters, 1981
- Graph Theory with Applications1976