Abstract
Set union-find problem is a classical problem in computer science. From VLSI channel routing to multiprocessor scheduling can all be reduced to set union-find problems. In large scale implementations like geographic information system are also important issue today. The set union-find problems has two types, online and offline. Different types of set union-find problems need different strategies to solve them. We introduce the best-known algorithms of online and offline set union-find problems under RAM model and external memory model. For the algorithm that executes an intermixed sequence of m union and find operations on n elements, the fastest known algorithm for online version under RAM model runs in O(mα(m + n), n) + n) time. The best-known algorithm of offline version under RAM model, which is proposed by Gabow and Tarjan, runs in O(m + n) time. In the external memory model, we measure the complexity by number of input and output between memory and the secondary storage. For the algorithm that executes an intermixed sequence of N not redundant union and find operations on set of elements, the optimal algorithm for offline external memory version runs in O( (m+n)/B logM/B (m+n)/B ) I/Os. In online external memory version, the current best result is by using Tarjan’s RAM model algorithm. The complexity is O(mα(m + n) + n) I/Os. Finally, we propose the study of set union-find problem in the Parallel Disk Model (PDM) as an important open problem, and identify the bottlenecks of solving such a problem using the existing techniques.