dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Bodlaender, prof. dr. H.L. | |
dc.contributor.advisor | van der Zanden MSc, T.C. | |
dc.contributor.author | Stewart, G.C.W. | |
dc.date.accessioned | 2020-02-20T19:03:38Z | |
dc.date.available | 2020-02-20T19:03:38Z | |
dc.date.issued | 2019 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/34842 | |
dc.description.abstract | 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. | |
dc.description.sponsorship | Utrecht University | |
dc.language.iso | en | |
dc.title | Parallel Algorithms on Tree Decompositions | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.courseuu | Computing Science | |