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.


References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Fampa, Marcia; Lee, Jon; Maculan, Nelson: An overview of exact algorithms for the Euclidean Steiner tree problem in $n$-space (2016)
  2. Leal do Forte, Vinícius; Tavares Montenegro, Flávio Marcelo; de Moura Brito, José André; Maculan, Nelson: Iterated local search algorithms for the Euclidean Steiner tree problem in $n$ dimensions (2016)
  3. Brazil, M.; Rubinstein, J.H.; Thomas, D.A.; Weng, J.F.; Wormald, N.: Gradient-constrained minimum networks. III: Fixed topology (2012)
  4. Van Laarhoven, Jon W.; Ohlmann, Jeffrey W.: A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in $\Re ^d $ (2011)
  5. Brazil, M.; Thomas, D.A.; Nielsen, B.K.; Winter, P.; Wulff-Nilsen, C.; Zachariasen, M.: A novel approach to phylogenetic trees: $d$-dimensional geometric Steiner trees (2009)
  6. Fampa, Marcia; Anstreicher, Kurt M.: An improved algorithm for computing Steiner minimal trees in Euclidean $d$-space (2008)
  7. Toppur, Badri; Smith, J.MacGregor: A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space (2005)
  8. Zachariasen, Martin: Local search for the Steiner tree problem in the Euclidean plane (1999)
  9. Smith, J.MacGregor; Toppur, Badri: Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in $E\sp 3$ (1996)
  10. Smith, Warren D.; Smith, J.MacGregor: On the Steiner ratio in 3-space (1995)
  11. Smith, Warren D.: How to find Steiner minimal trees in Euclidean $d$-space (1992)