Automatic Tuning of the SkewedKruskal Algorithm

The SkewedKruskal algorithm is an implementation of Kruskal algorithm where the edge list is recursively sorted on demand, mimicking the well-known QuickSort algorithm. We investigate the issue of improving the time performance of SkewedKruskal by guessing the position of the largest edge of a minimum cost spanning tree (MST), in order to avoid sorting unnecessary edges. For this purpose, a statistical analysis is performed on the distribution of the edge weights in some classes of randomly generated weighted graphs, so that the position of the largest MST edge can be guessed by sampling a relatively small number of edge weights. Experimental results are reported to evaluate the effectiveness of the techniques proposed.