How did Yao come up with his minimum spanning tree algorithm?

Question

I recently stumbled upon this text about Yao's algorithm for the minimum spanning tree (MST) and I was wondering if there are some preceding algorithms (other than Sollin's algorithm) that were published shortly before Yao's algorithm and that may have assisted (maybe some algorithms that grouped edges in a logarithmic number of groups) him in obtaining this result.

Flowi · Accepted Answer

I don't have a fully satisfactory answer, but maybe this helps.
Tarjan came up with an O(m log log n)-algorithm roughly at the same time. It's in this technical report:
http://www2.eecs.berkeley.edu/Pubs/TechRpts/1975/ERL-m-501.pdf
Yao says in his paper that Tarjan developed an O(m sqrt(log n)) algorithm, but it was not published. Maybe some of Tarjan's ideas influenced him, who knows.
I think Yao's algorithm is natural once a linear-time median-finding algorithm is available. Selection sort is very wasteful because we look at all the elements in each pass. Boruvka's (Sollin's) algorithm does something very similar, it determines the minimum edge per component in every phase. So we have to find some approximate ordering that allows us ignore some elements until later on.
Now there are two avenues that are "orthogonal" to each other:

Either partition the adjacency lists into "<="-ordered unsorted blocks with an algorithm for finding medians (or at least some good partition), and only look in the first block until it is used up, then continue with the next block.

Partition the adjacency lists into "packets" that have no order among them, but each of which is sorted, and compare the currently smallest elements from the packets. This is a viable alternative to Yao's approach and is in fact used to turn the Fredman-Tarjan algorithm into the Gabow-Galil-Spencer-Tarjan algorithm, where Fibonacci Heaps are used for the packets.

By the way, I think Yao made a small mistake in the case that m < n log n. He should use a contractive variant of Boruvka to reduce the number of vertices and avoid the union-find structure, which could incur a runtime of n log n or more even in the log log n phases, depending on the UF structure. One can contract in every of the log log n phases in linear time or possibly even run the simplest variant of the algorithm where the components are determined naively in every phase and contract once after the log log n Phases are finished. Then use Yao's trick with the blocks.

Hermann Gruber · Answer

Adding to Flowi's excellent answer, it seems that the main new ingredient in Yao's algorithm is a linear-time selection algorithm, which was new at the time.

I think Yao's algorithm is natural once a linear-time median-finding algorithm is available.

I found two sources confirming this. The first source is Chapter 6 "Minimum Spanning Trees" in Tarjan's book "Data Structures and Network Algorithms", SIAM 1983:

By judiciously implementing a Boruvka-like algorithm using the appropriate data structures, we can obtain a method that is faster on sparse graphs than is any of the classical algorithms. Yao [29] was the first to propose such a method. His algorithm runs in
O(m log log n) time but needs a linear-time selection algorithm [2], [24] and is thus not very practical.

The second source is Ronald L. Graham, Pavol Hell:
On the History of the Minimum Spanning Tree Problem. IEEE Ann. Hist. Comput. 7(1): 43-57 (1985)

A straightforward implementation of Algorithm 3 would run in time O(e log u), because each time the rule defining Algorithm 3 is applied, the number of fragments decreases by at least one-half. Yao [Yao75] has discovered an implementation of Algorithm 3 in time 0( e log log u) using the linear selection algorithm [BFPRT73].

How did Yao come up with his minimum spanning tree algorithm?

2 Answers

Add your own answers!

Ask a Question