Revision as of 06:16, 5 October 2004 edit Dcoetzee (talk \| contribs) 37,529 edits Added Chazelle, cleaned up <math>s ← Previous edit		Revision as of 07:55, 9 October 2004 edit undo Dcoetzee (talk \| contribs) 37,529 edits m Link Bernard Chazelle Next edit →
Line 11: Borůvka's algorithm can be shown to run in time [[Big O notation\|O]](''E''log ''V''), where ''E'' is the number of edges, and ''V'' is the number of vertices in ''G''. Other algorithms for this problem include [[Prim's algorithm]] and [[Kruskal's algorithm]]. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized version of Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected <math>O(E)</math> time. The best known minimum spanning tree algorithm by [[Bernard Chazelle]] is based on Borůvka's and runs in O(''E'' α(V)) time, where α is the inverse of the [[Ackermann function]]. [[Category:Graph algorithms]]

Borůvka's algorithm: Difference between revisions