Recovering a labeling algorithm for the disjoint-set problem to improve Kruskal's efficiency on dense graphs



This work recovers a fast labeling algorithm for the disjoint-set problem and shows that, specially for non-sparse graphs, this data structure is more efficient than the Disjoint-Set Union--and--Find method for implementing Kruskal's algorithm (that returns a minimum spanning tree of a given graph).
The latter data structure was introduced by Knuth in his classical trilogy on algorithms and is based on a special tree representation and path compression algorithms. Tarjan and van Leeuwen proved it to have an almost linear asymptotic complexity. We present bounds for the asymptotic behavior of the labeling algorithm and discuss the particularities that account for the difference in performance of either data structures implementations for Kruskal's algorithm. Several computational experiments using different versions of the canonical algorithm and the labeling one are presented and provide evidence supporting the theoretical conclusions.


Data Structures, Disjoint-set Problem, Spanning tree, Kruskal's algorithm, Performance and Efficiency


Graphs, Computational aspects of

TechReport Number


Cited by

No citations found