### 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 language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 618-629 |

Number of pages | 12 |

ISBN (Print) | 9783662447765 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland Duration: Sep 8 2014 → Sep 10 2014 |

### Publication series

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

Volume | 8737 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 22nd Annual European Symposium on Algorithms, ESA 2014 |
---|---|

Country | Poland |

City | Wroclaw |

Period | 9/8/14 → 9/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

*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