Borůvka's Algorithm

GPTKB entity

Statements (27)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
minimum spanning tree algorithm
gptkbp:alsoKnownAs Boruvka's algorithm
Borůvka algorithm
gptkbp:application clustering
network design
electrical grid design
gptkbp:complexity O(E log V)
gptkbp:field computer science
graph theory
gptkbp:first_published_year 1926
gptkbp:firstPublished gptkb:Práce_Moravské_Přírodovědecké_Společnosti
https://www.w3.org/2000/01/rdf-schema#label Borůvka's Algorithm
gptkbp:input connected, weighted, undirected graph
gptkbp:inventedBy gptkb:Otakar_Borůvka
1926
gptkbp:namedAfter gptkb:Otakar_Borůvka
gptkbp:output minimum spanning tree
gptkbp:property greedy algorithm
parallelizable
gptkbp:purpose find minimum spanning tree
gptkbp:relatedTo gptkb:Kruskal's_algorithm
gptkb:Prim's_algorithm
Reverse-Delete algorithm
gptkbp:step repeatedly add the cheapest edge from each component
gptkbp:bfsParent gptkb:Boruvka's_Algorithm
gptkbp:bfsLayer 7