Computing Steiner Points and Probability Steiner Points in ℓ1 and ℓ2 Metric Spaces

Abstract

The Steiner tree problem is a well known network optimization problem which asks for a connected minimum network (called a Steiner minimum tree) spanning a given point set N. In the original Steiner tree problem the given points lie in the Euclidean plane or space, and the problem has many variants in different applications now. Recently a new type of Steiner minimum tree, probability Steiner minimum tree, is introduced by the authors in the study of phylogenies. A Steiner tree is a probability Steiner tree if all points in the tree are probability vectors in a vector space. The points in a Steiner minimum tree (or a probability Steiner tree) that are not in the given point set are called St..