Skip to main content

Nested Set Union

Author(s): Larkin, Daniel H; Tarjan, Robert E

To refer to this page use:
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.
Publication Date: 2014
Citation: Larkin, Daniel H., and Robert E. Tarjan. "Nested Set Union." In European Symposium on Algorithms (2014): pp. 618-629. doi:10.1007/978-3-662-44777-2_51
DOI: 10.1007/978-3-662-44777-2_51
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 618 - 629
Type of Material: Conference Article
Journal/Proceeding Title: European Symposium on Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.