Statements (33)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Graph Theory Concept
|
| gptkbp:alsoKnownAs |
MST
|
| gptkbp:application |
Image segmentation
Approximation of NP-hard problems Cluster analysis Design of computer networks Design of electrical circuits Transportation networks |
| gptkbp:appliesTo |
gptkb:Undirected_Graph
Weighted Graph |
| gptkbp:complexityOfBoruvka |
O(E log V)
|
| gptkbp:complexityOfKruskal |
O(E log V)
|
| gptkbp:complexityOfPrim |
O(E + V log V)
|
| gptkbp:definedIn |
A spanning tree of a weighted, connected, undirected graph with minimum total edge weight
|
| gptkbp:firstDescribed |
gptkb:Otakar_Boruvka
1926 |
| https://www.w3.org/2000/01/rdf-schema#label |
Minimum Spanning Tree
|
| gptkbp:property |
Contains all vertices of the graph
Has minimum possible total edge weight Has no cycles Unique if all edge weights are distinct |
| gptkbp:relatedTo |
gptkb:Spanning_Tree
Graph Connectivity Shortest Path |
| gptkbp:supportsAlgorithm |
gptkb:Boruvka's_Algorithm
gptkb:Kruskal's_Algorithm gptkb:Prim's_Algorithm |
| gptkbp:usedIn |
Network Design
Clustering Approximation Algorithms |
| gptkbp:bfsParent |
gptkb:Spanning_Tree_Algorithm
gptkb:Graph_Algorithms |
| gptkbp:bfsLayer |
6
|