3 - The minimum spanning tree problem

Summary

A savage's mind is anything but defective. He is just a normal social animal whose chief interest in life is his relation to his neighbors.

A. M. Hocart, “Psychology and Ethnology”

The minimum spanning tree problem (MSTP) is a well-known topic in combinatorial optimization. We illustrate it with an instance of how to determine the monthly telephone charge to a generic large corporation G with offices in many cities, v₁, …, v_p. All the distances d(v_i, v_j) are known and are distinct. The corporation G does not wish to pay the phone company an amount proportional to the sum ∑d(v_i, v_j) of all the distances, since not all pairwise connections are needed for each office to be able to communicate with every other office. What is needed is a tree on these p nodes having minimum total distance.

In their definitive article on the history of the MSTP, Graham and Hell (1985) give three reasons for its popularity and importance. (1) It has efficient solutions that make it applicable to the analysis of large graphs, including graphs with thousands of nodes. (2) It has direct applications to the design of all kinds of networks, including communication, computer, transportation, wiring, flow, and other networks. (3) It has applications to numerous other problems, including network reliability, speech recognition, classification, and clustering. Graham and Hell also note that the greedy method common to MST algorithms is a source of many further applications.