Techniques in parameterized algorithm design
MetadataShow full item record
In this thesis we give a novel classification of techniques for designing parameterized algorithms, together with research publications applying these techniques, in particular Crown Decompositions, to various problems. In Part I we argue that the currently known techniques can be organized into just four general themes: Bounded Search Trees, Reduction Rules, Induction and Win/Win. The four main themes and their variations are presented through an algorithmic skeleton and illustrated by examples. Part II contains four research papers that apply the techniques described in Part I on the following problems: MAX INTERNAL SPANNING TREE, K3-PACKING, H-PACKING, K1;s-PACKING, P2-PACKING, SET SPLITTING, and MAX CUT. The techniques used include Win/Win, Bounded Search Trees, Greedy Localization, Crown Decomposition, Modelled Crown Decomposition, Extremal Method, and Reduction Rules.
Paper I: Reducing to Independent Set Stucture - the Case of k-INTERNAL SPANNING TREE, Prieto E., Sloper, C. published in Nordic Journal of Computing 12(2005), 308-318.Paper II: Looking at the stars. Theoretical Computer Science 2006 351(3): 437-445. Published version available at: http://dx.doi.org/10.1016/j.tcs.2005.10.009Paper III: Proceedings WG'04 - 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004), Bad Honnef, Germany,June 2004, Springer Verlag, Lecture Notes in Computer Science vol 3353, 235-244Paper IV: This paper appeared at the conference ’Algorithms and Complexity in Durham’, 2005 and has later been invited to a special issue of Journal of Discrete Algorithms