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

        Parallel Algorithms on Tree Decompositions

        Thumbnail
        View/Open
        Parallel_algorithms_on_tree_decompositions.pdf (359.0Kb)
        Publication date
        2019
        Author
        Stewart, G.C.W.
        Metadata
        Show full item record
        Summary
        Several problems including finding the maximum independent set and the minimum size dominating set of a graph are NP-hard problems that can be solved in linear time on graphs given with a tree decomposition whose width is bounded by a constant. So far, about all work on implementation of these algorithms was restricted to sequential algorithms, running on a CPU. A recent study showed that a GPU implementation of algorithms running on a path decomposition of a graph showed a significant speedup when compared to the CPU implementation. Both the GPU implementation for maximum independent set and minimum dominating set show a significant increase in speed on a subset of all tested tree decompositions, but do have an equal or a decreased performance on other trees. The tree decomposition the algorithm is ran on has a large influence on the performance of the algorithms.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/34842
        Collections
        • Theses
        Utrecht university logo