Dipartimento di Scienze Statistiche

In this paper we present a new two-phase algorithm able to generate the complete set of ecient solutions for the Bi-objective Minimum Spanning Tree (BMST) Problem. For the rst phase, we adopt two alternative methods: the dual variant of Benson's algorithm and the weighted sum method. The second phase consists in a new  enumerative recursive procedure that we propose based on the analysis of reduced costs. We tested the algorithm on dierent problem instances, including complete and grid graphs.