Recovering a labeling algorithm for the disjoint-set problem to improve Kruskal's efficiency on dense graphs
Authors
Abstract
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.