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

• Autorzy: Silva C. G. , Cli'maco J. C. N.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2007
• Tom: nr 4
• Strony: 11--15
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Silva C. G.

autor

Cli'maco J. C. N.

• Escola Superior de Tecnologia e Gest~ao de Leiria, Morro do Lena, Alto Vieiro, 2401-951 Leiria, Portugal,

Bibliografia

• [1] K. Andersen, K. J¨ornsten, and M. Lind, “On bicriterion minimal spanning trees: an approximation”, Comput. Oper. Res., vol. 23, pp. 1171–1182, 1996.
• [2] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows – Theory, Algorithms And Applications, New Yersey: Prentice Hall, 1993.
• [3] P. Camerini, G. Galbiati, and F Maffioli, “The complexity of multiconstrained spanning tree problems”, in Theory of Algorithms, Colloquium Pecs 1984, L. Lov´asz, Ed. Amsterdam: North-Holland, 1984, pp. 53–101.
• [4] J. Cohon, Multiobjective Programming and Planning. New York: Academic Press, 1978.
• [5] J. Cl´ımaco, J. Craveirinha, and M. Pascoal, “Multicriteria routing models in telecommunication networks – overview and a case study”, in Advances in Multiple Criteria Decision Making and Human Systems Management: Knowledge and Wisdom, Y. Shi, D. Olson, and A. Stam, Eds. Amsterdam: IOS Press, 2007, pp. 17–46.
• [6] M. Ehrgott and X. Gandibleux, “A survey and annoted bibliography of multiobjective combinatorial optimazation”, OR Spektrum, vol. 22, pp. 425–460, 2000.
• [7] H. W. Hamacher and G. Ruhe, “On spanning tree problems with multiple objectives”, Ann. Oper. Res., vol. 52, pp. 209–230, 1994.
• [8] R. M. Ramos, S. Alonso, J. Sicilia, and C. Gonz´alez, “The problem of the optimal biobjective spanning tree”, Eur. J. Oper. Res., vol. 111, pp. 617–628, 1998.
• [9] R. Tarjan, “Sensitivity analysis of minimum spanning trees and shortest path trees”, Inform. Proces. Lett., vol. 14, pp. 30–33, 1982.