The Steiner ratio of several discrete metric spaces (Q1861256): Difference between revisions

The author studies the greatest lower bound on the Steiner ratio \[ m(X,\rho)= \inf \left\{\frac{L(\text{SMT for }N)}{L(\text{MST for }N)}:\;N \text{ finite subset of }X,\text{ and }(X,\rho)\text{ metric space}\right\}, \] where SMT stands for Steiner minimal tree and MST for minimum spanning tree, and \(L\) is the length of the corresponding tree. He receives estimates and exact values for \(m(X,\rho)\) in several discrete spaces. Particularly, he determines the Steiner ratio for spaces of words and estimates the Steiner ratio for specific graphs.