Shortest Connection Networks And Some Generalizations

A problem of inherent interest in the planning of large-scale communication, distribution and transportation networks also arises in connection with the current rate structure for Bell System leased-line services. It is the following: Basic Problem -- Given a set of (point) terminals, connect them by a network of direct terminal-to-terminal links having the smallest possible total length (sum of the link lengths). (A set of terminals is "connected," of course, if and only if there is an unbroken chain of links between every two terminals in the set.) An example of such a Shortest Connection Network is shown in Fig. 1. The prescribed terminal set here consists of Washington and the forty-eight state capitals. The distances on the particular map used are accepted as true. Two simple construction principles will be established below which provide simple, straight-forward and flexible procedures for solving the basic problem. Among the several alternative algorithms whose validity follows from the basic construction principles, one is particularly well adapted for automatic computation. The nature of the construction principles and of the demonstration of their validity leads quite naturally to the consideration, and solution, of a broad class of minimization problems comprising a non-trivial abstraction and generalization of the basic problem. This extended class of problems contains examples of practical 1389