Skip navigation
Please use this identifier to cite or link to this item:
Title: Compressing Trees with a Sledgehammer
Authors: Larkin, Daniel
Advisors: Tarjan, Robert
Contributors: Computer Science Department
Keywords: algorithms
compressed trees
data structures
disjoint set union
nested set union
Subjects: Computer science
Issue Date: 2016
Publisher: Princeton, NJ : Princeton University
Abstract: A variety of problems can be solved more efficiently with the use of compressed trees. The compressed tree method is flexible and can be applied in different ways to solutions for many problems including disjoint set union, nested set union, and path evaluation. The central contribution of this thesis is a unified framework for the analysis of the compressed tree method and a meta-theorem that proves an inverse-Ackermann-type bound for a class of algorithms. The meta-theorem requires only that the compaction method be well-structured and that the other operations maintain a forest structure that admits a well-behaved rank function. These are the weakest known conditions of any analysis to-date that proves such a bound. We use the framework to give a clean, compact alternative analysis of all but one of the known efficient algorithms for disjoint set union; we provide an explicit proof of optimality for the remaining known optimal method, splicing by rank, which was left as an exercise by Tarjan and van Leeuwen; we prove that a new algorithm for disjoint set union called randomized linking is optimal, giving theoretical backing for some recent experimental results; and finally we proceed to explore the nested set union problem, giving an optimal algorithm for any constant number of partitions as well as a few alternatives for the restricted case of two partitions.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Larkin_princeton_0181D_11599.pdf687.28 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.