@inproceedings{fd9b119fe7e2469687a40ab057939153,
title = "Nested set union",
abstract = "We consider a version of the classic disjoint set union (union-find) problem in which there are two partitions of the elements, rather than just one, but restricted such that one partition is a refinement of the other. We call this the nested set union problem. This problem occurs in a new algorithm to find dominators in a flow graph. One can solve the problem by using two instances of a data structure for the classical problem, but it is natural to ask whether these instances can be combined. We show that the answer is yes: the nested problem can be solved by extending the classic solution to support two nested partitions, at the cost of at most a few bits of storage per element and a small constant overhead in running time. Our solution extends to handle any constant number of nested partitions.",
keywords = "data structures, disjoint set union, union-find",
author = "Larkin, {Daniel H.} and Tarjan, {Robert E.}",
year = "2014",
doi = "10.1007/978-3-662-44777-2_51",
language = "English (US)",
isbn = "9783662447765",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "618--629",
booktitle = "Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings",
address = "Germany",
note = "22nd Annual European Symposium on Algorithms, ESA 2014 ; Conference date: 08-09-2014 Through 10-09-2014",
}