• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Techniques in parameterized algorithm design

Sloper, Christian
Doctoral thesis
Thumbnail
Åpne
Paper 4 (98.94Kb)
Paper 3 (113.5Kb)
Paper 2 (129.7Kb)
Paper 1 (121.2Kb)
Main Thesis (512.0Kb)
Permanent lenke
https://hdl.handle.net/1956/1112
Utgivelsesdato
2006-03-06
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [742]
Sammendrag
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.
Består av
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.009

Paper 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-244

Paper 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
Utgiver
The University of Bergen

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit