MSc Thesis Defense by Tyler Huffman – Københavns Universitet

MSc Thesis Defense by Tyler Huffman

Titel

A Survey of Dynamic Tree Data Structures and an Implementation of an Amortized Top Tree

Abstract

In the field of dynamic connectivity, this thesis aims to provide an implementation of
an amortized top tree using two other fully dynamic data structures; Sleator-Tarjan trees, and topology trees. In addition, this thesis provides a new configuration of a topology tree, using the height and running time bounds described in Sleator-Tarjan trees.

Supervisor: Christian Wulff-Nilsen

Co-supervisor: Eva Rotenberg 

Censor: Rasmus Pagh, professor, ITU