A top tree data structure solves one of the most general variants of a well- studied dynamic trees problem consisting in maintenance of a tree along with some aggregated information on paths or in individual trees, possibly in a mutable way, under operations of inserting and removing edges. It provides a simple interface separated from both an internal top tree structure representing a hierarchical partitioning of the graph, and a driver ensuring its depth to be logarithmic, which has a crucial role for the efficiency of the data structure. The driver proposed in this thesis is based on biased trees, combining techniques used in the worst-case version of link/cut trees and in the amortized driver for top trees: An input forest is decomposed into heavy paths and interleaving vertices, all of them being represented by biased trees connected together to form exactly the top tree structure. The driver is meant to be a more efficient alternative to the originally proposed one, and a comparably efficient alternative to the driver proposed by Werneck; there is a room for their experimental comparison.
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:388131 |
| Date | January 2018 |
| Creators | Ondráček, Lukáš |
| Contributors | Majerech, Vladan, Fink, Jiří |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0042 seconds