Maximum Leaf Spanning Tree Problem Benchmarks

This database contains experimental problems designed to study the Maximum Leaf Spanning Tree Problem (MLSTP). More specifically, the dataset can be used to evaluate the performance of algorithms developed to solve MLSTP. We generated a set of large-scale instances. We also collected existing benchmarks {Lucena, A., Maculan, N. & Simonetti, L. Reformulations and solution algorithms for the maximum leaf spanning tree problem. Comput Manag Sci 7, 289–311 (2010). https://doi.org/10.1007/s10287-009-0116-5, GENDRON, B., LUCENA, A., DA CUNHA, A. S. & SIMONETTI, L. (2014), "Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem", INFORMS Journal on Computing, 26, 645-657, doi: https://doi.org/10.1287/ijoc.2013.0589.} which were included in the dataset.

These instances are used in a study entitled “A New Formulation and Algorithm for Maximum Leaf Spanning Tree Problem with an Application in the Forest Fire Detection” which will be appeared in ----.

DOI reference: http://dx.doi.org/10.17632/w98s4tvfn8.1