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
Climaco, J., and Martins, E.Q.V., "A bicriterion shortest path algorithm", European Journal of Operational Research, 11 (1982) 399−404.
Cook, W., Cunningham, W., Pulleyblank, W., and Schrijver, A., Combinatorial Optimization, Series in Discrete Mathematics and Optimization, Wiley-Interscience, 1998.
Cvetković, D., Kovačević-Vujčić, V., (eds.), Combinatorial Optimization − Mathematical Theory and Algorithms, Yugoslav Operational Research Society, Belgrade, 1996. (in Serbian)
Ehtgott, M., Multicriteria Optimization, Springer-Verlag, 2000.
Ehrgott, M., and Gandibleux, X., "An annotated bibliography of multiobjective combinatorial optimization", Report in Wissenschaftmathematik Nr 62/2000, Universitat Kaiserslautern, 2000. www.mathematik.uni-kl.de
Harris Jr., F.C., "Steiner minimal trees: An introduction, parallel computation and future work", in: D.-Z. Du, P. M. Pardalos (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1998.
Ivanov, A.O., and Tuzhelin, A.A., Minimal Networks: The Steiner Problem and Its Generalizations, CRC Press, 1994.
Ulungu, E.L., and Teghem, J., "Multi-objective combinatorial optimization problems: A survey", Journal of Multi-Criteria Decision Analysis, 3 (1994) 83−104.
Vujošević, M., and Stanojević, M., "Bottleneck Steiner tree problem", EURO XVII, 17th European Conference on Operational Research, Budapest, July 16−19, 2000.
Vujošević, M., and Stanojević, M., "Multiobjective travelling salesman problem and a fuzzy set approach to solving it", Application of Mathematics in Engineering and Economics, 27 (2002) 111−118.
Warme, D.M., Winter, P., and Zachariasen, M., "Exact algorithm for plane Steiner tree problems: A computational study", in: D.-Z. Du, M. Smith, J. H. Rubinstein (eds.), Advances in Steiner Trees, Kluwer Academic Publishers, 1998.
Steiner tree bibliography, http://www.ganley.org/steiner/steinerbib.html
Downloads
Published
Issue
Section
License
Copyright (c) 2003 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.