Computing steiner minimum trees in Hamming metric

摘要

Computing Steiner minimum trees in Hamming metric is a well studied problem that has applications in several fields of science such as computational linguistics and computational biology. Among all methods for finding such trees, algorithms using variations of a branch and bound method developed by Penny and Hendy have been the fastest for more than 20 years. In this paper we describe a new pruning approach that is superior to previous methods and its implementation.