Optimality conditions in preference-based spanning tree problems

  1. Miguel Ángel Domínguez-Ríos
  2. Sergio Alonso 1
  3. Colebrook Santamaría, Marcos 1
  4. Antonio Sedeño-Noda 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

Aktak:
Operational Research Peripatetic Post-Graduate Programme (ORP3)

Argitaletxea: ESMAP S.L.

ISBN: 84-689-3077-6

Argitalpen urtea: 2005

Orrialdeak: 195-200

Biltzarra: Operational Research Peripatetic Post-Graduate Programme (ORP3)

Mota: Biltzar ekarpena

Laburpena

Spanning trees problems defined in apreference-based environment are addressed. In thisapproach, optimality conditions for the well-knownminimum-weight spanning tree problem are generalizedto be used with more general preference orders. Then,necessary and/or sufficient properties of the preferencerelations are studied, in order to assure that the set of‘most preferred’ trees is the set of spanning treesverifying the optimality conditions. Finally, an algorithmfor the construction of the set of spanning trees fulfillingthe optimality conditions is designed.