Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/91455
Type: Artigo de periódico
Title: Reformulations And Solution Algorithms For The Maximum Leaf Spanning Tree Problem
Author: Lucena A.
Maculan N.
Simonetti L.
Abstract: Given a graph G = (V, E), the maximum leaf spanning tree problem (MLSTP) is to find a spanning tree of G with as many leaves as possible. The problem is easy to solve when G is complete. However, for the general case, when the graph is sparse, it is proven to be NP-hard. In this paper, two reformulations are proposed for the problem. The first one is a reinforced directed graph version of a formulation found in the literature. The second recasts the problem as a Steiner arborescence problem over an associated directed graph. Branch-and-Cut algorithms are implemented for these two reformulations. Additionally, we also implemented an improved version of a MLSTP Branch-and-Bound algorithm, suggested in the literature. All of these algorithms benefit from pre-processing tests and a heuristic suggested in this paper. Computational comparisons between the three algorithms indicate that the one associated with the first reformulation is the overall best. It was shown to be faster than the other two algorithms and is capable of solving much larger MLSTP instances than previously attempted in the literature. © 2010 Springer-Verlag.
Editor: 
Rights: fechado
Identifier DOI: 10.1007/s10287-009-0116-5
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-77954087471&partnerID=40&md5=c1f35f6bc13f03ab19635e045fac04ff
Date Issue: 2010
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-77954087471.pdf315 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.