Boruvka Meets Nearest Neighbors

Abstract. Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka’s al-gorithm by using nearest neighbors search structures to significantly re-duce time and memory consumption. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algo-rithms on large low-dimensional datasets by several orders of magnitude.