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