TY - GEN

T1 - Nested set union

AU - Larkin, Daniel H.

AU - Tarjan, Robert Endre

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958552206&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958552206&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44777-2_51

DO - 10.1007/978-3-662-44777-2_51

M3 - Conference contribution

AN - SCOPUS:84958552206

SN - 9783662447765

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 618

EP - 629

BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 22nd Annual European Symposium on Algorithms, ESA 2014

Y2 - 8 September 2014 through 10 September 2014

ER -