FindSteinerTree

FindSteinerTree is a program for computing Steiner Trees in multiple dimensions, written by Christian Peter Klingenberg. It is an implementation of the algorithm described by Warren D. Smith (Smith, W. D. 1992. How to find Steiner minimal trees in Euclidean d-space. Algorithmica 7:137–177). This algorithm uses a branch-and-bound approach. It will therefore find the optimal tree, but the computational effort increases very rapidly with increasing numbers of data points. Smith’s algorithm uses Euclidean distance as the minimizing criterion. It therefore computes the tree that connects the data points entered with tree that has the shortest possible sum of branch lengths measured as Euclidean distance (Euclidean Steiner tree). In addition to this, the program also can use the sum of squared branch lengths as the criterion (Squared-change Steiner tree). This is an extension of Smith’s algorithm useful, for example, in phylogenetic studies where squared-change parsimony is much more widely used than the Euclidean criterion. Users can choose one of these options on the opening screen of the program.