MST的cheriton-tarjan算法的複雜性

Question

幾天前我在這裏看到一篇關於Cheriton-Tarjan算法的文章，我認爲這是對Boruvka算法的改進。我想我知道它是如何工作的，但我不明白爲什麼這個算法的複雜性是O（mloglogn）。有人可以向我解釋嗎？日Thnx。

Answer 1

確實，這個算法的複雜度是O（mlog（logn））。閱讀這篇文章here，我想你會明白算法及其複雜性

Answer 2

Here is a reference to the 1976 paper and the complexity you quote 
is only for some worse case situations. There are other complexities 
quoted for other conditions. 

Finding Minimum Spanning Trees 

Related Databases 
Web of Science 
You must be logged in with an active subscription to view this. 
Article Data 
History 
Submitted: 10 June 1975 
Published online: 13 July 2006 
Keywords 
equivalence algorithm, graph algorithm, minimum spanning tree, priority queue 
Digital Object Identifier 
http://dx.doi.org/10.1137/0205051 
Publication Data 
ISSN (print): 0097-5397 
ISSN (online): 1095-7111 
Publisher: Society for Industrial and Applied Mathematics 
David Cheriton and Robert Endre Tarjan 

This paper studies methods for finding minimum spanning trees in graphs. 
Results include 1. several algorithms with $O(m\log \log n)$ worst-case 
running times, where n is the number vertices and m is the number of 
edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense 
graphs (those for which m is $\Omega (n^{1 + \varepsilon })$ for some 
positive constant $\varepsilon $); 3. an $O(n)$ worst-case algorithm 
for planar graphs; 4. relationships with other problems which might 
lead general lower bound for the complexity of the minimum spanning tree 
problem. 

Copyright © 1976 Society for Industrial and Applied Mathematics 

Read More: http://epubs.siam.org/doi/abs/10.1137/0205051