ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05C05, 52A21 Cieslik, Dietmar, University of Greifswald, Germany The Steiner Ratio of Metric Spaces The “Problem of shortest connectivity”, usually called Steiner’s Problem, is to find for a finite set of points in a metric space a tree interconnecting these points with minimal length. Where as this problem is very hard as well in combinatorial as in computational sense, the determination of a Minimum Spanning Tree is simple. The greatest lower bound for the ratio between the lengths of these both trees for the same set of points is called the Steiner ratio (of the space). It will be present a overview of the exact value and lower or upper bounds for the value of the Steiner ratio in many metric spaces, particularly in finite-dimensional Banach spaces. It will be show how the geometric properties of the space hace an influence of the Steiner ration. References: D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers,