Melzak algorithm for phylogenetic spaces (Q1405934)

The authors present an algorithm for constructing a minimal tree \(\Gamma\) of given topology \(G\) involving a finite subset \(N=\{\beta_1,\dots,\beta_n\}\) of a phylogenetic space. The algorithm velocity is of order of \(2^n| \beta_1| \cdots| \beta_n| \), where \(| \beta| \) is a length of the word \(\beta\). An algorithm for constructing the Simpson-Torrichelli point for the set \(N\) is obtained as a corollary as well as an algorithm for constructing a minimal Steiner tree for a three-point set.