Experimental Evaluation on Union-Find Algorithms for the Disjoint-Set Data Structure
- Speaker:
- Mostofa Patwary (University of Bergen)
- Date / time:
- Tuesday, April 27, 2010, 10:00
- Location:
- Buys Ballot Laboratory, Room 165, Utrecht (BBL 165)
Abstract
The disjoint-set data structure is used to maintain a collection of non-overlapping sets of elements from a finite universe. Algorithms that operate on this data structure are often referred to as Union-Find algorithms. They are used in numerous practical applications and are also available in several software libraries. This talk presents an extensive experimental study comparing the time required to execute 55 variations of Union-Find algorithms. The study includes all the classical algorithms, several recently suggested enhancements, and also different combinations and optimizations of these. Our results clearly show that a somewhat forgotten simple algorithm developed by Martin Rem in 1976 is the fastest, in spite of the fact that its worst-case time complexity is inferior to that of the commonly accepted “best” algorithms.