On the bicriterion - minimal cost/minimal label - spanning tree problem

We address a bicriterion spanning tree problem relevant in some application fields such as telecommunication networks or transportation networks. Each edge is assigned with a cost value and a label (such as a color). The first criterion intends to minimize the total cost of the spanning tree (the summation of its edge costs), while the second intends to get the solution with a minimal number of different labels. Since these criteria, in general, are conflicting criteria we developed an algorithm to generate the set of non-dominated spanning trees. Computational experiments are presented and results discussed. © 2009 Elsevier B.V. All rights reserved.