1. Home page
  2. Search

Partial Orderings and Algorithms on Graphs

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Partial Orderings and Algorithms on Graphs
Γιαννοπούλου Αρχοντία (EL)
born_digital_thesis
Διδακτορική Διατριβή (EL)
Doctoral Dissertation (EN)
2013
Στις εργασίες Ελασσόνων Γραφημάτων, οι N. Robertson και P. Seymour απέδειξαν μια σειρά από δομικά και αλγοριθμικά αποτελέσματα. Κάποια \mbox{από} αυτά, όπως το Ισχυρό  και το Ασθενές Δομικό Θεώρημα, το Θεώρημα Απαγορευμένης Σχάρας καθώς και ο αλγόριθμος για την Περιεκτικότητα Ελάσσονος, αποτελούν πλούσια πηγή πολλών ακόμα δομικών αλλά και  αλγοριθμικών αποτελεσμάτων.Επιπλέον, η ανάπτυξη της Θεωρίας Ελασσόνων Γραφημάτων συνέπεσε και επηρέασε την ανάπτυξη ενός νέου κλάδου της πολυπλοκότητας, την Θεω\-ρία Παραμετρικής Πολυπλοκότητας, που προτάθηκε από τους R. Downey και M. Fellows. Σε αυτή την διδακτορική διατριβή ασχολούμαστε με μια σειρά από ζητήματα της Θεωρίας Ελασσόνων Γραφημάτων και της Θεωρίας Παραμετρικής Πολυπλοκότητας καθώς και με την  αλληλεξάρτηση των δύο αυτών περιοχών. (EL)
In the Graph Minors project, N. Robertson and P. Seymour, proved a series of structural and  algorithmic results. Some of them, such as the Strong and the Weak Structure Theorem, the Excluded  Grid Theorem and the algorithm for Minor Containment, constitute a rich source of many more structural  as well as algorithmic results. Furthermore, the development of Graph Minor Theory coincided with and influenced the development  of a new branch of Complexity, namely the Parameterized Complexity Theory, introduced by R. Downey  and M. Fellows. In this doctoral thesis we deal with a series of issues in Graph Minor Theory and Parameterized  Complexity as well as the dependence of these two areas.  (EN)
English
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Τομέας Μαθηματικής Ανάλυσης
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Doctoral Dissertation



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)