Is this dense version of Kruskal's algorithm well-known?

Question

About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we achieve $\Theta(n^2)$ in all cases, similar to Prim's when implemented using adjacency matrices.

I've posted a bit about the algorithm in my blog, including C++ code and benchmarks, but here's the general idea:

• Maintain one representative node for each connected component. Initially, all nodes represent themselves.

• Maintain a vector dist[i] such that, for every component i, has the lightest component-crossing edge incident to i.

• When finding the lightest edge that crosses partitions, simply find i that minimizes the weight of dist[i], in linear time.

• When joining two components $c_i$ and $c_j$, modify the adjacency matrix $A$, such that now $A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$ for all components $k$, and mark $i$ as no longer representative of its connected component (only $j$ will now remain).

The contracting of the lightest edge and the finding of said edge can thus both be done in linear time. We do this $n - 1$ times to find the MST. A little bookkeeping is needed to actually find which edge we want to add to the MST, but does not increase the complexity. Thus the runtime is $\Theta(n^2)$. The implementation is just a couple of for loops.

Is this version of Kruskal well-known in the literature?

Answer 1

I'm not sure about this specific method for achieving $O(n^2)$ time, but two different methods for performing Kruskal in $O(n^2)$ time are given in my paper "Fast hierarchical clustering and other applications of dynamic closest pairs" (SODA 1998, arXiv:cs.DS/9912014, and J. Experimental Algorithms 2000):

1. Use Prim–Dijkstra–Jarník instead and then sort the edges to get the insertion sequence that Kruskal would give, or

2. Use the quadtree closest-pair data structure described in the paper, viewing Kruskal as a standard agglomerative clustering procedure where we merge the closest two clusters into a supercluster at each step, with "closest" defined as the length of the shortest edge connecting two clusters.

Solution 2 is similar in spirit to what you describe but the details of how to keep track of the distances between clusters are slightly different. You keep the row-wise minima of the cluster distance matrix, allowing you to scan this list of row-minima in linear time to find the global minimum, while my paper overlays a quadtree on the same matrix and keeps track of the minimum in each quadtree square. Your method is simpler, but less flexible for some other dynamic closest pair problems (it depends on the fact that merging two clusters causes their distances to other clusters to decrease, true for this problem but not necessarily for others).

As I wrote in 2011 in the Wikipedia article on the nearest-neighbor chain algorithm, that algorithm can also be used to perform Kruskal in $O(n^2)$ time. However (unlike some other applications of the nearest-neighbor chain algorithm) you don't get a space savings, so (like the quadtree method and your method) the space is still $O(n^2)$. In contrast Prim+sorting can use only $O(n)$ space beyond that needed to store the input.