A bicriterion Steiner tree problem on graph
DOI:
https://doi.org/10.2298/YJOR0301025VKeywords:
Steiner tree, bicriterion optimization, bottleneck problem, lexicographic methodAbstract
This paper presents a formulation of bicriterion Steiner tree problem which is stated as a task of finding a Steiner tree with maximal capacity and minimal length. It is considered as a lexicographic multicriteria problem. This means that the bottleneck Steiner tree problem is solved first. After that, the next optimization problem is stated as a classical minimums Steiner tree problem under the constraint on capacity of the tree. The paper also presents some computational experiments with the multicriteria problem.References
*** Steiner tree bibliography. http://www.ganley.org/steiner/steinerbib.html
Climaco, J., Martins, E.Q.V. (1982) A bicriterion shortest path algorithm. European Journal of Operational Research, 11, 4, 399-404
Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A. (1998) Combinatorial optimization, series in discrete mathematics and optimization. New York, itd: Wiley-Interscience
Cvetković, D.M., Kovačević-Vujčić, V.V. (1996) Combinatorial optimization - mathematical theory and algorithms. Belgrade: Yugoslav Operational Research Society, in Serbian
Ehrgott, M., Gandibleux, X. (2000) An annotated bibliography of multiobjective combinatorial optimization. Universität zu Kaiserslautern, Report in Wissenschaftmathematik Nr 62/2000
Ehtgott, M. (2000) Multicriteria optimization. Berlin, itd: Springer Verlag
Harris, Jr., F.C. (1998) Steiner minimal trees: An introduction, parallel computation and future work. u: D.-Z. Du, P.M.Pardalos [ur.] Handbook of Combinatorial Optimization, Dordrecht, itd: Kluwer Academic
Ivanov, A.O., Tuzhelin, A.A. (1994) Minimal networks: The steiner problem and its generalizations. Boca Raton, FL, itd: CRC Press
Ulungu, E.L., Teghem, J. (1994) Multi-objective combinatorial optimization problems: A survey. Journal of Multi-Criteria Decision Analysis, 3, 83-104
Vujošević, M., Stanojević, M. (2000) Bottleneck Steiner tree problem. u: EURO XVII, 17th European Conference on Operational Research, Budapest, July 16-19
Vujošević, M., Stanojević, M. (2002) Multiobjective traveling salesman problem and a fuzzy set approach to solving é. Application of Mathematics in Engineering and Economics, 27, 111-118
Warme, D.M., Winter, P., Zachariasen, M. (1998) Exact algorithm for plane Steiner tree problems: A computational study. u: D.-Z. Du, M.Smith, J.H.Rubinstein [ur.] Advances in Steiner Trees, Dordrecht, itd: Kluwer Academic
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
