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 algorithm due to Karger, Klein and Tarjan runs in O(m) time, where m is the number of edges in the graph.
Search Encyclopedia
|
Featured Article
|