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 compute SMT’s in parallel.
Secondly We look at future work in the computation of Steiner Minimal Trees.