View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Dynamic programming on Nice Tree Decompositions

        Thumbnail
        View/Open
        thesis_lwgraaff_v2.pdf (633.2Kb)
        Publication date
        2015
        Author
        Graaff, L.W. van der
        Metadata
        Show full item record
        Summary
        Connectivity problems such as the Steiner Tree Problem are NP-hard problems that are fixed parameter tractable in the treewidth of the input graph. In this thesis a dynamic programming algorithm on nice tree decompositions is discussed. Based on observations on nice tree decomposition diversity and experiment results, a number of optimization heuristics are proposed to speed up computation. By restructuring the nice tree decomposition, all tested input graphs show a considerable improvement both in amount of processed partial solutions as well as computation time. Furthermore a number of different data structures are analyzed, that allow for various constant time operations for graphs of low treewidth.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/19547
        Collections
        • Theses
        Utrecht university logo