Steiner Minimal Trees: Their Computational Past, Present, and Future

: Given a set of N cities, construct a connected network which has minimum length. The problem is simple enough, but the catch is that you are allowed to add junctions in your network. Therefore the problem becomes how many extra junctions should be added, and where should they be placed so as to minimize the overall network length. This intriguing optimization problem is known as the Steiner Minimal Tree Problem (SMT), where the junctions that are added to the network are called Steiner Points. The focus of this paper is twofold. First we look at the computational history of the problem, up through and including a new method to computer SMT's in parallel. Secondly we look at future work in the computation of Steiner Minimal Trees. keywords: Steiner Minimal Trees 1 Introduction Minimizing a network's length is one of the oldest optimization problems in mathematics and, consequently, it has been worked on by many of the leading mathematicians in history. In the mid-seventeenth century..