• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Worst case driver pro Top stromy / Worst case driver for Top trees

Ondráček, Lukáš January 2018 (has links)
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.

Page generated in 0.0646 seconds