Algoritmos para la construcción del conjunto de árboles generadores bajo un sistema de preferencia: condiciones y diseño
- Miguel Ángel Domínguez-Ríos 1
- Sergio Alonso 1
- Marcos Colebrook 1
- Antonio Sedeño-Noda 1
-
1
Universidad de La Laguna
info
- Joaquín Sicilia Rodríguez (ed. lit.)
- Carlos González Martín (ed. lit.)
- Miguel Ángel González Sierra (ed. lit.)
- David Alcaide López de Pablo (ed. lit.)
ISBN: 84-689-8553-8
Año de publicación: 2006
Páginas: 405-406
Tipo: Aportación congreso
Resumen
Presentamos aquí la fase nal del estudio de las condiciones necesariasy sucientes a exigir a los sistemas de preferencia denidos sobresubconjuntos de aristas de un grafo conexo, para que los árbolesgeneradores más preferidos veriquen ciertas condiciones de optimalidad.El cumplimiento de tales condiciones facilita la labor de diseño dealgoritmos para la construcción de los árboles generadores más preferidosy constituye una elegante generalización del problema del árbol generadorde mínimo coste.
Referencias bibliográficas
- R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows. Theory, Algorithms and Applications. Prentice Hall, 1993.
- P. Perny and O. Spanjaard, "A preference-based approach to spanning trees and shortest path problems", in European Journal of Operational Research, vol. 162, issue 3, pages 584-601, May 2005.
- R. M. Ramos, S. Alonso, J. Sicilia and C. González, "The problem of the optimal biobjective spanning tree" in European Journal of Operational Research, vol. 111(3), pages 617-628, 1998