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

        Cut and Count and Representative Sets on Branch Decompositions

        Thumbnail
        View/Open
        Thesis V2.pdf (681.2Kb)
        Publication date
        2016
        Author
        Pino, W.J.A.
        Metadata
        Show full item record
        Summary
        Recently, new techniques have been introduced to speed up dynamic programming algorithms on tree decompositions for connectivity problems: the `Cut and Count' method and a method called the rank-based approach, based on representative sets and Gaussian elimination. These methods respectively give randomized and deterministic algorithms that are single exponential in the treewidth, and respectively polynomial and linear in the number of vertices. In this thesis, these methods are adapted to branch decompositions. This yields algorithms, both randomised and deterministic, that are in many cases faster than when tree decompositions would be used. In particular, the currently fastest randomised algorithms for several problems on planar graphs are obtained. When the involved weights are O(n^O(1)), this thesis presents faster randomised algorithms on planar graphs for Steiner Tree, Connected Dominating Set, Feedback Vertex Set and TSP, and a faster deterministic algorithm for TSP. When considering planar graphs with arbitrary real weights, faster deterministic algorithms for all four mentioned problems are obtained.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/23660
        Collections
        • Theses
        Utrecht university logo