Complexity of union-split-find problems
Katherine Jane Lai · DSpace@MIT (Massachusetts Institute of Technology) · 2008
In this thesis, we investigate various interpretations of the Union-Split-Find problem, an extension of the classic Union-Find problem. In the Union-Split-Find problem, we maintain disjoint sets of ordered elements subject to the operations of constructing singleton sets, merging two sets together, splitting a set by partitioning it around a specified value, and finding the set that contains a given element. The different interpretations of this problem arise from the different assumptions made regarding when sets can be merged and any special properties the sets may have. We define and analyze the Interval, Cyclic, Ordered, and General Union-Split-Find problems. Previous work implies optimal solutions to the Interval and Ordered Union-Split-Find problems and an Ω(log n / log log n) lower bound for the Cyclic Union-Split-Find problem in the cell-probe model. We present a new data