摘要
Set union-find 問題是電腦科學的經典問題之一,從VLSI到多核心處理器的排程問題都和 set union-find 問題有關。 一些需要處理大量資訊的問題像是地理資訊系統也會用到 set union-find 的概念。 Set union-find 問題分為兩種,online 和 offline。不同的問題種類解決的策略也不同。 我們介紹不同模型下的 online 和 offline 問題。 對於 n 個元素執行 m 個混合的 union 或 find 指令,在 RAM model 下目前最快的 online 演算法時間複雜度為O(mα(m + n), n) + n)。 最快的 RAM model offline 演算法時間複雜度為O(m + n),由 Gabow 和 Tarjan 提出。 在 external memory model 下,我們關注的是資料在記憶體和外部儲存空間之間的輸入或輸出量。 在此模型下目前最快的 offline 演算法複雜度為O( (m+n)/B logM/B (m+n)/B ) I/Os。 而最快的 online 演算法是利用 Tarjan 和 Gabow 在 RAM model 提出的演算法,其複雜度為O(mα(m + n) + n) I/Os。 最後,我們也進行了 set union-find 問題在 parallel disk model (PDM) 上的研究,這目前是重要的開放問題。 如果要利用目前的技術解決這個問題,會有一些困難,我們找出了這個解決方向的瓶頸,可以進一步的研究解決。
並列摘要
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.