Borůvka's algorithm


Borůvka's algorithm

Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.

It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. [cite journal | last = Borůvka | first = Otakar | authorlink = Otakar Borůvka | year = 1926 | title = O jistém problému minimálním (About a certain minimal problem) | journal = Práce mor. přírodověd. spol. v Brně III | volume = 3 | pages = 37–58 | language = Czech, German summary ] [cite journal | last = Borůvka | first = Otakar | authorlink = 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–154 | language = Czech ] The algorithm was rediscovered by Choquet in 1938; [cite journal | last = Choquet | first = Gustave | authorlink = 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–313 | language = French ] again by Florek, Łukasiewicz, Perkal, Steinhaus, 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, this algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

The algorithm begins by examining each vertex and adding the cheapest edge from that vertex to another in the graph, without regard to already added edges, and continues joining these groupings in a like manner until a tree spanning all vertices is completed. Designating each vertex or set of connected vertices a "component", pseudocode for Borůvka's algorithm is:

*Begin with a connected graph "G" containing edges of distinct weights, and an empty set of edges "T"
*While the vertices of "G" connected by "T" are disjoint:
**Begin with an empty set of edges "E"
**For each component:
***Begin with an empty set of edges "S"
***For each vertex in the component:
****Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to "S"
***Add the cheapest edge in "S" to "E"
**Add the resulting set of edges "E" to "T".
*The resulting set of edges "T" is the minimum spanning tree of "G"

Borůvka's algorithm can be shown to take O(log "V") iterations of the outer loop until it terminates, and therefore to run in time O("E"log "V"), where "E" is the number of edges, and "V" is the number of vertices in "G". In planar graphs, 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. [citation|last=Eppstein|first=David|authorlink=David Eppstein|contribution=Spanning trees and spanners|title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor2-first=J.|editor2-last=Urrutia|publisher=Elsevier|year=1999|pages=425–461; citation|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.]

Other algorithms for this problem include Prim's algorithm (actually discovered by Vojtěch Jarník) and Kruskal's algorithm. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized minimum spanning tree algorithm based in part on Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected O(E) time. The best known (deterministic) minimum spanning tree algorithm by Bernard Chazelle is also based in part on Borůvka's and runs in O("E" α(V)) time, where α is the inverse of the Ackermann function. These randomized and deterministic algorithms combine steps of Borůvka's algorithm, reducing the number of components that remain to be connected, with steps of a different type that reduce the number of edges between pairs of components.

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Otakar Borůvka — (10 May 1899 in Uherský Ostroh – 22 July 1995 in Brno) was a Czech mathematician best known today for his work in graph theory, long before this was an established mathematical discipline. He was born in Uherský Ostroh, a town in Moravia (then in …   Wikipedia

  • Kruskal's algorithm — is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is… …   Wikipedia

  • Prim's algorithm — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Reverse-delete algorithm — The reverse delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge weighed graph. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected… …   Wikipedia

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

  • Levenberg–Marquardt algorithm — In mathematics and computing, the Levenberg–Marquardt algorithm (LMA)[1] provides a numerical solution to the problem of minimizing a function, generally nonlinear, over a space of parameters of the function. These minimization problems arise… …   Wikipedia

  • Gauss–Newton algorithm — The Gauss–Newton algorithm is a method used to solve non linear least squares problems. It can be seen as a modification of Newton s method for finding a minimum of a function. Unlike Newton s method, the Gauss–Newton algorithm can only be used… …   Wikipedia

  • Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Timeline of algorithms — The following timeline outlines the development of algorithms (mainly mathematical recipes ) since their inception.Before Modern Era* Before Writing about recipes (on cooking, rituals, agriculture and other themes) * c. 1600 BC Babylonians… …   Wikipedia