Revision as of 20:04, 29 December 2005 edit 65.57.245.11 (talk) Fixed an error in the description of the algorithm ← Previous edit		Revision as of 09:04, 8 January 2006 edit undo Charles Matthews (talk \| contribs) Autopatrolled, Administrators 367,914 edits mNo edit summary Next edit →
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]], [[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:

Borůvka's algorithm: Difference between revisions