About: Borůvka's algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Borůvka's algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,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.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

Attributes	Values
rdf:type	software
rdfs:label	Borůvka's algorithm (en)
rdfs:comment	Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,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.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. (en)
sameAs	Borůvka's algorithm
dbp:wikiPageUsesTemplate	dbt:Math dbt:Short_description dbt:Graph_search_algorithm
Subject	Articles with example pseudocode Spanning tree Graph algorithms
thumbnail	wiki-commons:Special:FilePath/Boruvka's_algorithm_(Sollin's_algorithm)_Anim.gif?width=300
foaf:depiction
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Borůvka's_algorithm?oldid=1068478044&ns=0
Wikipage page ID	197253 (xsd:integer)
page length (characters) of wiki page	10953 (xsd:nonNegativeInteger)
Wikipage revision ID	1068478044 (xsd:integer)
Link from a Wikipage to another Wikipage	Greedy algorithm Ackermann function Bernard Chazelle Big O notation Moravia Articles with example pseudocode Spanning tree Jan Łukasiewicz Graph algorithms Kruskal's algorithm Hugo Steinhaus Planar graph Prim's algorithm Component (graph theory) Minimum spanning tree Otakar Borůvka Parallel computing Electrical grid Graph minor Gustave Choquet Total order Memory address dbr:Julian_Perkal dbr:Kazimierz_Florek dbr:Stefan_Zubrzycki
has abstract	Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,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.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. 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.Then, it repeats a similar process of finding the minimum-weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest.Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Borůvka's_algorithm
is Wikipage redirect of	Boruvka's algorithm Boruvka algorithm Boruvkas algorithm Borůvka algorithm Sollin's algorithm Sollins Sollins algorithm
is Link from a Wikipage to another Wikipage of	Distributed minimum spanning tree 1926 in science Algorithm Boruvka's algorithm David Karger Kruskal's algorithm Hugo Steinhaus List of graph theory topics List of multiple discoveries List of people from Moravia List of algorithms Minimum spanning tree Graph theory Expected linear time MST algorithm Euclidean minimum spanning tree Boruvka algorithm Boruvkas algorithm Borůvka algorithm
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Borůvka's_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software