Talk:Kruskal's algorithm

Many problems with this proof. Confusion between vertices and edges, etc., etc.. --zero 05:56, 13 Oct 2003 (UTC)

There was actually also a problem with the running time. Kruskal's can run in O(|E| log |V|) where E is the set of edges and V the set of vertices. It should be obvious that |E| >= |V| in any graph that connects all vertices (though not necessarily fully connected).

Hell, using a better UNION-FIND paradigm, Kruskal's algorithm will run in expected time $O(|E|\alpha (|E|))$, where $\alpha$ is the inverse Ackermann function. (If memory serves right. It's certainly better than $O(|E|\log |V|)$). Grendelkhan 08:46, 2004 Apr 20 (UTC)

Merge the min spanning tree algorithms into one article

The three pages Kruskal's algorithm, Boruvka's algorithm and Prim's algorithm should be merged into one article (possibly named minimum weight spanning tree algorithm), because they are all very similar greedy algorithms (the underlying concept is the same, they only differ, if at all, in use of data structures), which were discovered independently. Also, there are some other confusions. Jarnik, mentioned in Prim's algorithm, cooperated on this problem with Boruvka, so they should be mentioned on the same page. Also, originally, their definiton of "graph" (for this problem) was a set of points in Euclidean space, and the weights were distances among points and the tree was called skeleton (the lightest possible construction needed to rigidly connect the points - so, due to this tradition, in Czech, the problem is called "problem of minimum skeleton"). So, if anyone doesn't object to this, I'll try to merge them. Samohyl Jan 17:29, 11 Jan 2005 (UTC)

I don't think they need to be merged. Each is already mentioned in the Minimum spanning tree article and they seem different enough to have their own articles. Cockroachbill

It may be worthwhile merging Kruskal's with Prim's, as these are pretty similar, but Boruvka's is (I think) different. After all, textbooks often treat them simultaneously. Even for those two, I could go either way. The "minimum skeleton" you refer to is now called the Euclidean minimum spanning tree, which has its own article, and in fact has considerably more efficient specialized algorithms than any of these three. Consider adding a redirect. Deco 18:33, 1 December 2005 (UTC)