The Skewed Kruskal Algorithm

Kruskal algorithm is one of the most efficient algorithms to compute a minimum spanning tree (MST) of a given weighted unoriented and connected graph. The edge list is sorted and edges are iteratively selected from it until a MST is found. To improve its performance, edge sorting can be interleaved with edge selection, so that only the relevant part of the edge list is actually sorted. Filtering techniques can also be used so that the size of some parts of the edge list is reduced before sorting and selection. Here we examine a further idea, i.e. to produce an unbalanced initial partition, with the aim of early guessing which part of the edge list actually needs being considered for filtering, sorting and edge selection.