Μερικές διατάξεις και αλγόριθμοι σε γραφήματα

Abstract

In the Graph Minors project, N. Robertson and P. Seymour, proveda series of structural and algorithmic results. Some of them, such as theStrong and the Weak Structure Theorem, the Excluded Grid Theoremand the algorithm for Minor Containment, constitute a rich source ofmany more structural as well as algorithmic results.Furthermore, the development of Graph Minor Theory coincided withand inuenced the development of a new branch of Complexity, namelythe Parameterized Complexity Theory, introduced by R. Downey and M.Fellows.In this doctoral thesis we deal with a series of issues in Graph MinorTheory and Parameterized Complexity as well as the dependence of thesetwo areas.