An I/O Efficient Algorithm for Minimum Spanning Trees

摘要

An O(Sort(E)·log log_(E/V) B) I/Os algorithm for computing a minimum spanning tree of a graph G = (V, E) is presented, where Sort(E) = (E/B)log_(M/B)(E/B), M is the main memory size, and B is the block size. This improves on the previous bound of O(Sort(E)·log log(VB/E)) I/Os by Arge et al. for all values of V, E and B, for which I/O optimality is still open. In particular, our algorithm matches the lowerbound Ω(E/V·Sort(V)), when E/V ≥ B~∈ for a constant ∈ > 0, an O(log log B) factor improvement over the algorithm of Arge et al. Our algorithm can compute the connected components too, for the same number of I/Os, which is an improvement on the best known upper bound.