Partial Orderings and Algorithms on Graphs

Γιαννοπούλου Αρχοντία

Μονάδα:

Τομέας Μαθηματικής Ανάλυσης
Βιβλιοθήκη Σχολής Θετικών Επιστημών

Ημερομηνία κατάθεσης:

2013-04-15

Έτος εκπόνησης:

2013

Συγγραφέας:

Γιαννοπούλου Αρχοντία

Στοιχεία επταμελούς επιτροπής:

Δημήτριος Μ. Θηλυκός Αναπληρωτής Καθηγητής

Πρωτότυπος Τίτλος:

Partial Orderings and Algorithms on Graphs

Γλώσσες διατριβής:

Αγγλικά

Μεταφρασμένος τίτλος:

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

Περίληψη:

Στις εργασίες Ελασσόνων Γραφημάτων, οι N. Robertson και P. Seymour απέδειξαν
μια σειρά από δομικά και αλγοριθμικά αποτελέσματα. Κάποια \mbox{από} αυτά, όπως
το Ισχυρό
και το Ασθενές Δομικό Θεώρημα, το Θεώρημα Απαγορευμένης Σχάρας καθώς και ο
αλγόριθμος για την Περιεκτικότητα Ελάσσονος, αποτελούν πλούσια πηγή πολλών
ακόμα δομικών αλλά και
αλγοριθμικών αποτελεσμάτων.Επιπλέον, η ανάπτυξη της Θεωρίας Ελασσόνων
Γραφημάτων συνέπεσε και επηρέασε την ανάπτυξη ενός νέου κλάδου της
πολυπλοκότητας, την Θεω\-ρία Παραμετρικής Πολυπλοκότητας, που προτάθηκε από
τους R. Downey και M. Fellows. Σε αυτή την διδακτορική διατριβή ασχολούμαστε με
μια σειρά από ζητήματα της Θεωρίας Ελασσόνων Γραφημάτων και της
Θεωρίας Παραμετρικής Πολυπλοκότητας καθώς και με την
αλληλεξάρτηση των δύο αυτών περιοχών.

Λέξεις-κλειδιά:

Θεωρία Ελασσόνων Γραφημάτων, Ανίχνευση Γραφημάτων, Θεώρημα Αποκλεισμένης Σχάρας, Θεωρία Δισδιαστατότητας, Δεντροπλάτος

Ευρετήριο:

Ναι

Αρ. σελίδων ευρετηρίου:

XV-XVII, XIX, 297-304

Εικονογραφημένη:

Ναι

Αρ. βιβλιογραφικών αναφορών:

222

Αριθμός σελίδων:

XX, 304