Parallel computation of Steiner minimal trees
J. S. Harris · TigerPrints (Clemson University) · 1995
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 foundation of this thesis is a parallel algorithm for the generation of what Pawel Winter termed T-list and its implementation. This generation of T-list is followed by the extraction of the proper answer. When Winter developed his algorithm, the time for extraction dominated the overall computation time. After Cockayne and Hewgill's work, the time to generate T-list dominated the overall computation time. The parallel algorithms we present were implemented in a program called PARSTEINER94, and the results show that the time to generate T-list has now been cut by an order of magnitude. So now the extraction time once again dominates the overall computation time. We also present a characterization of SMT's for certain size grids. The characterization of the SMT for a 2 x m grid is known. In this work we present that characterization as well as conjectured characterizations of SMT's for 3 x m and 4 x m grids.