Boruvka's Algorithm

GPTKB entity

Statements (27)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
minimum spanning tree algorithm
gptkbp:alsoKnownAs gptkb:Borůvka's_Algorithm
gptkb:Sollin's_Algorithm
gptkbp:complexity O(E log V)
gptkbp:field computer science
graph theory
gptkbp:firstPublished gptkb:Práce_Moravské_Přírodovědecké_Společnosti
1926
https://www.w3.org/2000/01/rdf-schema#label Boruvka's Algorithm
gptkbp:input connected, weighted, undirected graph
gptkbp:inventedBy gptkb:Otakar_Borůvka
1926
gptkbp:notableFor historical significance
parallelizability
gptkbp:output minimum spanning tree
gptkbp:purpose find minimum spanning tree
gptkbp:relatedTo gptkb:Kruskal's_Algorithm
gptkb:Prim's_Algorithm
gptkbp:step merge components
repeat until one component remains
repeatedly add the cheapest edge from each component
gptkbp:usedIn electrical engineering
telecommunications
network design
gptkbp:bfsParent gptkb:Spanning_Tree_Algorithm
gptkbp:bfsLayer 6