DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
reformulations and solution algorithms for the max leaf spanning tree problem

 

The Max Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree of a given graph G = (V;E) where the number of leaves is as large as possible. The problem has applications, among others, in the design of  telecommunication networks. In this presentation, we describe two very simple MLSTP reformulations that allowed us to solve, to proven optimality, instances of the problem twice as large as those found in the literature.