Borůvka's algorithm: Difference between revisions

Revision as of 23:56, 8 February 2006

Revision as of 23:57, 8 February 2006

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 [[Bohemia]]. The algorithm was rediscovered by [[Choquet]] in 1938; again by [[Florek]], [[Lukasiewicz|Jan Łukasiewicz|Lukasiewicz]], [[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: