A note on the computation of ordered supported non-dominated solutions in the bi-criteria minimum spanning tree problems

Abstract

This paper presents a new procedure for computing the set of supported non-dominated solutions of bi-criteria minimum spanning tree problems in ordered manner. The procedure is based on the systematic detection of edges which must be replaced in one efficient solution to obtain the adjacent one, in the criteria space. This new approach avoids solving unnecessary problems and makes use of previous computations.

Keywords

• minimum spanning tree
• supported non-dominated solutions
• combinatorial problems