δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Στις εργασίες Ελασσόνων Γραφημάτων, οι 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)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
