Great papers: On the shortest spanning subtree of a graph and the traveling salesman problem

I’ve decided to read and summarize one great paper a week from this list. This week’s paper is the 1956 paper On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem by the late Joseph Kruskal.

Summary:

First, this is an extremely short paper–barely exceeding 2 pages. Talk about an (important) MPU!

In this paper, Kruskal outlines what is now known as Kruskal’s algorithm for finding a minimum spanning tree. It was not, however, the first. In his $O(m \log{n})$ algorithm, he begins to add least cost edges to (an originally edgeless) graph, so long as no cycle is created. Kruskal claims that this algorithm is simpler than the “unnecessarily elaborate” construction of Borůvka. It provides an alternate proof that the MST is unique when the edge lengths are distinct.

He also provides another algorithm for MST (he calls it Construction A’), which seems to be exactly the reverse-delete algorithm. At this time, the Wikipedia page on reverse-delete does not credit Kruskal (nor anyone else).

After seeing “traveling salesman problem” (TSP) in the title, I was expecting Kruskal to discuss the relationship between MST and TSP. Surprisingly, though, he only mentions that the two are “closely related.” Not another word appears about the TSP.

As an aside, Kruskal had a reputable academic family–on multiple accounts. Several blood-relatives, including his brothers and nephew,  became famous statisticians, mathematical physicists, and computer scientists. His academic family was also strong. His advisors were Albert W. Tucker (of KKT fame) and Roger Lyndon, and Paul Erdős seems to have played an important role as well. Kenneth Appel (of 4-color theorem fame) was his academic half-brother.

Next up:

• M. Grötschel, L. Lovász, and A. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization, Combinatorica 1 (1981), 169.
• M. Grötschel, L. Lovász, and A. Schrijver, Corrigendum to our Paper “The Ellipsoid Method and its Consequences in Combinatorial Optimization”, Combinatorica 4 (1984), 291.