Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp011g05ff012
 Title: Compressing Trees with a Sledgehammer Authors: Larkin, Daniel Advisors: Tarjan, Robert Contributors: Computer Science Department Keywords: algorithmscompressed treesdata structuresdisjoint set unionnested set unionunion-find 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. URI: http://arks.princeton.edu/ark:/88435/dsp011g05ff012 Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: http://catalog.princeton.edu/ Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Computer Science

Files in This Item:
File Description SizeFormat