Optimality conditions in preference-based spanning tree problems
Date:
September 06-10, 2005. Co-authored with Domínguez-Ríos MA, Alonso S and Sedeño-Noda A. ISBN 84-689-3077-6, pages 197-200.
Abstract
Spanning trees problems defined in a preference-based environment are addressed. In this approach, optimality conditions for the well-known minimum-weight spanning tree problem are generalized to be used with more general preference orders. Then, necessary and/or sufficient properties of the preference relations are studied, in order to assure that the set of ‘most preferred’ trees is the set of spanning trees verifying the optimality conditions. Finally, an algorithm for the construction of the set of spanning trees fulfilling the optimality conditions is designed.