Content deleted Content added
m added link to the page for "minimum spanning tree" |
add "randomized" and "expected" to KKT algorithm |
||
Line 3:
Borůvka's algorithm can be shown to run in time O(m log n), where m is the number of edges, and n is the number of vertices.
Other algorithms for this problem include [[Prim's algorithm]] and [[Kruskal's algorithm]]. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized algorithm due to Karger, Klein and Tarjan runs in expected O(m) time, where m is the number of edges in the graph.
| |||