Borůvka's algorithm: Difference between revisions

Revision as of 03:49, 15 November 2005

Revision as of 20:53, 24 December 2005

Line 1:

'''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 [[MoraviaBohemia]]. The algorithm was rediscovered by [[Choquet]] in 1938; again by [[Florek]], [[Lukaziewicz]], [[Perkal]], [[Stienhaus]], and [[Zubrzycki]] in 1951; and again by [[Sollin]] some time in the early 1960s. Because [[Sollin]] was the only Western computer scientist in this list—[[Choquet]] was a civil engineer; [[Florek]] and his co-authors were anthropologists—this algorithm is frequently but incorrectly called ‘[[Sollin]]’s algorithm’, especially in the parallel computing literature.

Borůvka's algorithm, in pseudocode, given a connected graph ''G'', is:

Line 11:

Other algorithms for this problem include [[Prim's algorithm]] (actually discovered by [[Vojtech Jarnik]]) 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]]