Quantitative Analysis for Management, 13/e

9.6 Minimal-Spanning Tree Problem

The minimal-spanning tree problem involves connecting all points of a network together while minimizing the total distance of these connections. Some common examples include telephone or cable companies trying to connect houses in a neighborhood, and network administrators trying to minimize the cable required to hardwire computers in a network. While a linear programming model can be used for this problem, it has certain properties that make this quite complex. Fortunately, there is another method for finding the solution to such a problem that is very easy, and that will be presented here. The minimal-spanning tree technique problem will be presented using the following example.

Let us consider the Lauderdale ...