Top trees thesis

As my master thesis on the MFF UK I chose this implementation/experimental topic. My task was to implement two different approaches to build and maintain Top trees and then I have to compare them on difficult hard problems like 2-edge connectivity.

And what are these Top trees?

In my thesis I described them as…

Top Trees are not so well known data structure which could be used to maintain information of some dynamically updated collection of trees. User of this data structure defines four basic operations, which are used internally when Top Trees structure is changing. When there occurs some cutting or joining on underlying trees the structure updates internally stored information using these user functions.

This data structure could be used for example to dynamically maintain diameter, center or median (minimizing weighted distance from all other vertices) of given tree in time O(log N) (where N denotes the number of vertices).

For more information (and pictures) see my Master thesis (included below).

My work

I implemented two different drivers for the Top trees structure: