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

Authors

DOI:

https://doi.org/10.26636/jtit.2007.4.845

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

References

[1] K. Andersen, K. Jornsten, and M. Lind, “On bicriterion minimal spanning trees: an approximation", Comput. Oper. Res., vol. 23, pp. 1171-1182, 1996.
View in Google Scholar

[2] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows - Theory, Algorithms And Applications, New Jersey: Prentice Hall, 1993.
View in Google Scholar

[3] P. Camerini, G. Galbiati, and F. Maffioli, "The complexity of multi constrained spanning tree problems", in Theory of Algorithms, Colloquium Pecs 1984, L. Lovasz, Ed. Amsterdam: North-Holland, 1984, pp. 53-101.
View in Google Scholar

[4] J. Cohon, Multiobjective Programming and Planning. New York: Academic Press, 1978.
View in Google Scholar

[5] J. Climaco, 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.
View in Google Scholar

[6] M. Ehrgott and X. Gandibleux, "A survey and annotated bibliography of multiobjective combinatorial optimization", OR Spektrum, vol. 22, pp. 425-460, 2000.
View in Google Scholar

[7] H. W. Hamacher and G. Ruhe, "On spanning tree problems with multiple objectives", Ann. Oper. Res., vol. 52, pp. 209-230, 1994.
View in Google Scholar

[8] R. M. Ramos, S. Alonso, J. Sicilia, and C. Gonzalez, "The problem of the optimal biobjective spanning tree", Eur. J. Oper. Res., vol. 111, pp. 617-628, 1998.
View in Google Scholar

[9] R. Tarjan, "Sensitivity analysis of minimum spanning trees and shortest path trees", Inform. Proces. Lett., vol. 14, pp. 30-33, 1982.
View in Google Scholar

Downloads

Published

2007-12-30

Issue

No. 4 (2007)

Section

RESEARCH ARTICLES

License

Copyright (c) 2023 Journal of Telecommunications and Information Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
C. Gomes da Silva and J. C. Clímaco, “A note on the computation of ordered supported non-dominated solutions in the bi-criteria minimum spanning tree problems”, JTIT, vol. 30, no. 4, pp. 11–15, Dec. 2007, doi: 10.26636/jtit.2007.4.845.