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.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I don't have a fully satisfactory answer, but maybe this helps.
First one should note that 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 slow because we look at all remaining elements in each pass in order to determine the minimum. Boruvka's (Sollin's) algorithm does something very similar, it determines the minimum outgoing edge per component in every phase. If we find some "approximate" ordering of the outgoing edges that allows us to ignore some elements until later on, we can speed up the algorithm. Now there are two avenues that are "orthogonal" to each other:
Either partition the edges into blocks whose content is unsorted, but the blocks are "$\leq$"-ordered. This can be done using an algorithm for finding medians (in a quicksort with optimal pivots that stops the recursion once the desired block size is reached). Then we only look for the minimum edge in the first block until it is used up, then continue with the next block and so on.
Or partition the adjacency lists into "packets" that have no order among them, but each of packet is sorted (what you get when stopping the Merge Sort recursion once the desired packet size is reached). Then compare the currently smallest elements from all packets. The packet whose edge is the smallest then moves on to the second-largest, and so on. This is a viable alternative to Yao's approach, which uses 1., and is in fact used to turn the Fredman-Tarjan algorithm into the Gabow-Galil-Spencer-Tarjan algorithm, (but more complicated since Fibonacci Heaps are used for the packets in order to make them meldable).
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. Then use Yao's trick with the blocks. (Once might even first run the simplest variant of the algorithm where the components are determined naively in every phase and contract only once after the $\log \log n$ Phases are finished.)
$\begingroup$
$\endgroup$
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].
