Borůvka's algorithm: Difference between revisions

Revision as of 04:36, 12 September 2020

Revision as of 13:28, 10 January 2021

Line 5:

or a minimum spanning forest in the case of a graph that is not connected.

It was first published in 1926 by [[Otakar Borůvka]] as a method of constructing an efficient [[electricity network]] for [[Moravia]].<ref>{{cite journal | last = Borůvka | first = Otakar | authorlinkauthor-link = Otakar Borůvka | year = 1926 | title = O jistém problému minimálním |trans-title=About a certain minimal problem | journal = Práce Mor. Přírodověd. Spol. V Brně III | volume = 3 | pages = 37–58 | url = https://dml.cz/handle/10338.dmlcz/500114 | language = Czechcs, Germande}}</ref><ref>{{cite journal | last = Borůvka | first = Otakar | authorlinkauthor-link = Otakar Borůvka | year = 1926 | title = Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks) | journal = Elektronický Obzor | volume = 15 | pages = 153&ndash;154 | language = Czechcs }}</ref><ref>{{cite journal

| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil

| last2 = Milková | first2 = Eva

Line 19:

| hdl-access = free

}}</ref>

The algorithm was rediscovered by [[Gustave Choquet|Choquet]] in 1938;<ref>{{cite journal | last = Choquet | first = Gustave | authorlinkauthor-link = Gustave Choquet | year = 1938 | title = Étude de certains réseaux de routes | journal = Comptes Rendus de l'Académie des Sciences | volume = 206 | pages = 310&ndash;313 | language = Frenchfr }}</ref> again by [[Kazimierz Florek|Florek]], [[Jan Łukasiewicz|Łukasiewicz]], [[Julian Perkal|Perkal]], [[Hugo Steinhaus|Steinhaus]], and [[Stefan Zubrzycki|Zubrzycki]] in 1951;<ref>{{cite journal

| last1 = Florek | first1 = K.

| last2 = Łukaszewicz | first2 = J. | author2-link = Jan Łukasiewicz

Line 26:

| last5 = Zubrzycki | first5 = S.

| journal = Colloquium Mathematicae

| language = Frenchfr

| mr = 0048832

| pages = 282–285

Line 32:

| url = https://eudml.org/doc/209969

| volume = 2

| year = 1951}}</ref> and again by Georges Sollin in 1965.<ref>{{cite journal | last = Sollin | first = Georges | year = 1965 | title = Le tracé de canalisation | journal = Programming, Games, and Transportation Networks | language = Frenchfr }}</ref> This algorithm is frequently called '''Sollin's algorithm''', especially in the [[parallel computing]] literature.

The algorithm begins by finding the minimum-weight edge incident to each vertex of the graph, and adding all of those edges to the forest.

Line 64:

== Complexity ==

Borůvka's algorithm can be shown to take [[Big O notation|O]](log ''V'') iterations of the outer loop until it terminates, and therefore 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''. In [[planar graph]]s, and more generally in families of graphs closed under [[graph minor]] operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm.<ref>{{Cite book|last=Eppstein|first=David|authorlinkauthor-link=David Eppstein|contribution=Spanning trees and spanners|title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link= Jorge Urrutia Galicia|publisher=Elsevier|year=1999|pages=425–461|postscript=<!--None-->}}; {{Cite journal|last=Mareš|first=Martin|title=Two linear time algorithms for MST on minor closed graph classes|journal=Archivum Mathematicum|volume=40|year=2004|issue=3|pages=315–320|url=http://www.emis.de/journals/AM/04-3/am1139.pdf|postscript=<!--None-->}}.</ref>

== Example ==