Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorGroenland, C.E.
dc.contributor.authorVlas, Jorke de
dc.date.accessioned2023-08-10T00:02:50Z
dc.date.available2023-08-10T00:02:50Z
dc.date.issued2023
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/44574
dc.description.abstractThis 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.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectThis thesis, written in paper format, shows that the Perfect Phylogeny problem is complete for the parameterized complexity class XALP.
dc.titleOn the parameterized complexity of the Perfect Phylogeny problem
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsperfect phylogeny;triangulated graphs;XALP;parameterized complexity;W-hierarchy
dc.subject.courseuuMathematical Sciences
dc.thesis.id21500


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record