The Steiner ratio of several discrete metric spaces

AbstractSteiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:m(X,ρ)≔infL(SMTforN)L(MSTforN):N⊆Xisafiniteset,which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs