A bicriterion Steiner tree problem on graph

Authors

  • Mirko B. Vujošević Laboratory for Operational Research, Faculty of Organizational Sciences University of Belgrade, Belgrade, Serbia and Montenegro
  • Milan Stanojević Laboratory for Operational Research, Faculty of Organizational Sciences University of Belgrade, Belgrade, Serbia and Montenegro

DOI:

https://doi.org/10.2298/YJOR0301025V

Keywords:

Steiner tree, bicriterion optimization, bottleneck problem, lexicographic method

Abstract

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

2003-03-01

Issue

Section

Research Articles