The Filter-Kruskal Minimum Spanning Tree Algorithm
Vitaly Osipov, Peter W. Sanders, Johannes Singler · Society for Industrial and Applied Mathematics eBooks · 2009
We present Filter-Kruskal -a simple modification of Kruskal's algorithm that avoids sorting edges that are "obviously" not in the MST.For arbitrary graphs with random edge weights Filter-Kruskal runs in time O m + n log n log m n , i.e. in linear time for not too sparse graphs.Experiments indicate that the algorithm has very good practical performance over the entire range of edge densities.An equally simple parallelization seems to be the currently best practical algorithm on multicore machines.