Nested set union

Daniel H. Larkin, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages618-629
Number of pages12
ISBN (Print)9783662447765
DOIs
StatePublished - Jan 1 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
CountryPoland
CityWroclaw
Period9/8/149/10/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Nested set union'. Together they form a unique fingerprint.

  • Cite this

    Larkin, D. H., & Tarjan, R. E. (2014). Nested set union. In Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings (pp. 618-629). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8737 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-44777-2_51