Optimality conditions in preference-based spanning tree problems

Abstract

Spanning tree problems defined in a preference-based environment are addressed. In this approach, optimality conditions for the minimum-weight spanning tree problem (MST) are generalized for use with other, more general preference orders. The main goal of this paper is to determine which properties of the preference relations are sufficient to assure that the set of ‘most-preferred’ trees is the set of spanning trees verifying the optimality conditions. Finally, algorithms for the construction of the set of spanning trees fulfilling the optimality conditions are designed, improving the methods in previous papers.