Parallel computation of the Pareto frontier for the bi-objective minimum spanning tree problem

This talk presents a parallel algorithm for the bi-objective minimum spanning tree (BMST) problem which takes advantage of a two-phase procedure for the generation of a complete set of efficient solutions. The first phase involves computing the extreme supported efficient solutions by resorting to an algorithmic approach (Prim embedded in a dichotomic search), while the second phase focuses on determining the non-extreme supported and non-supported efficient solutions. In this latter phase, all spanning trees of a connected graph are generated through edge interchanges based on increasing evaluation of reduced costs of associated weighted linear programs. The results of preliminary computational experiments will be discussed.