dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Bodlaender, H.L. | |
dc.contributor.advisor | Leeuwen, E.J. van | |
dc.contributor.author | Kuipers, R. | |
dc.date.accessioned | 2017-11-27T18:02:00Z | |
dc.date.available | 2017-11-27T18:02:00Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/28084 | |
dc.description.abstract | The Co-Path/Cycle Packing problem that tries to find a set of vertices that, when removed, leaves a graph of maximum degree 2 is a prominent problem in the graph theory field. The related Vertex Cover problem, which finds a deletion set where the remaining graph has maximum degree 0, is one of the most famous graph theory problems. In this thesis we describe a deterministic parameterized algorithm for Co-Path/Cycle Packing which uses branch-and-bound techniques. This algorithm is shown to have a time complexity of O*(3.0607^k), which improves upon the previous best known deterministic bound. A new problem which looks for a deletion set such that the remaining graph is 2-regular is also discussed, and a branching algorithm with time-bound O*(3^k) is shown for it. Additionally, two variants of these two problems that add the requirement that the remaining graph is a single connected component are introduced and shown to both have an algorithm that runs in O(2^k * n^3) time. For the three new problems, NP-completeness is also proven. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 633947 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.title | Deterministic branching algorithms for parameterized Co-Path/Cycle Packing and three variants | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Co-Path/Cycle Packing, Co-Cycle Packing, Induced Cycle Deletion Set, Induced Path/Cycle Deletion Set, Induced Cycle Deletion, Induced Path/Cycle Deletion, Bounded-Degree-d, Bounded-Degree-2, BDD, BDD-2, Vertex deletion, parameterized, branching, FPT, CPCP | |
dc.subject.courseuu | Computing Science | |