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 Implementations on the GPU of Algorithms for the Minimum Dominating Set Problem Using Dynamic Programming on Tree Decompositions.

        Thumbnail
        View/Open
        Thesis.pdf (442.1Kb)
        Publication date
        2019
        Author
        Jimkes, T.A.
        Metadata
        Show full item record
        Summary
        Two different algorithms that solve the Minimum Dominating Set problem are implemented in both a sequential, and parallel fashion. The first on the CPU, and the latter using GPU programming. The aim of this work is to find out to what extent these algorithms can be implemented on the GPU, and how these four different implementations compare on different instances. The experimental results show that when the tree width k grows, parallelization of these algorithms provides reductions in run time that can reach multiple orders of magnitude. The sequential implementations do outperform their parallel counterparts for very small bag sizes, due to the overhead associated with the GPU implementations.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/33651
        Collections
        • Theses
        Utrecht university logo