4
$\begingroup$

The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. The algorithm relies on the fact that leftist heaps can be merged in time O(log n), but also uses the fact that leftist heaps are binary trees and therefore that every node has at most two children.

In 1978, binomial heaps were invented as a cleaner type of heap that supports merging in O(log n) time. Since then, most algorithms that need mergable heaps either use binomial heaps or some other related structure. However, since binomial heaps don't use binary trees, the Cheriton-Tarjan algorithm's main optimization (namely, eliminating unnecessary edges by doing a top-down DFS over the heap) won't work in the same time bounds when run on a binomial heap rather than a leftist heap.

Has there been any work done to update the Cheriton-Tarjan MST algorithm to use binomial heaps rather than leftist heaps?

Thanks!

Improve this question
$\endgroup$
  • $\begingroup$ According to Google Scholar, there are 38 papers that cite the original Cheriton-Tarjan paper that contain the word "binomial". A careful search through those might provide an answer. I don't see any likely candidates, but questions like these are always hard to answer confidently in the negative. $\endgroup$ – jbapple Sep 16 '19 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.