Borůvka's algorithm: Difference between revisions

Revision as of 10:40, 16 January 2005

Revision as of 21:04, 21 March 2005

Line 1:

[[Category:Trees (structure)]]

'''Borůvka's algorithm''' is an [[algorithm]] for finding [[minimum spanning tree]]s. It was first published in [[1926]] by [[Otakar Borůvka]] as a method of constructing an efficient electricity network for [[Bohemia]].

Line 12 ⟶ 11:

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&#367;vka's. A faster randomized version of Bor&#367;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&#367;vka's and runs in O(''E'' &alpha;(V)) time, where &alpha; is the inverse of the [[Ackermann function]].

[[Category:Trees (structure)]]

[[Category:Graph algorithms]]

[[Category:Optimization algorithms]]