dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Groenland, C.E. | |
dc.contributor.author | Vlas, Jorke de | |
dc.date.accessioned | 2023-08-10T00:02:50Z | |
dc.date.available | 2023-08-10T00:02:50Z | |
dc.date.issued | 2023 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/44574 | |
dc.description.abstract | This thesis categorizes the parameterized complexity of the algorithmic problems Perfect Phylogeny and Triangulating Colored Graphs. We show that they are complete for the parameterized complexity class XALP using a reduction from Tree-chained Multicolor Independent Set and a proof of membership. We introduce the problem Triangulating Multicolored Graphs as a stepping stone and prove XALP-completeness for this problem as well. We also show that, assuming the Exponential Time Hypothesis, there exists no algorithm that solves any of these problems in time f(k)n^{o(k)}, where n is the input size, k the parameter, and f any computable function. | |
dc.description.sponsorship | Utrecht University | |
dc.language.iso | EN | |
dc.subject | This thesis, written in paper format, shows that the Perfect Phylogeny problem is complete for the parameterized complexity class XALP. | |
dc.title | On the parameterized complexity of the Perfect Phylogeny problem | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | perfect phylogeny;triangulated graphs;XALP;parameterized complexity;W-hierarchy | |
dc.subject.courseuu | Mathematical Sciences | |
dc.thesis.id | 21500 | |