Μονάδα:
Τμήμα ΜαθηματικώνΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2018-06-15
Συγγραφέας:
Μανιάτης Σπυρίδων
Στοιχεία επταμελούς επιτροπής:
Χρήστος Α. Αθανασιάδης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Μιχάλης Δρακόπουλος, Επίκουρος Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Λευτέρης Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Ιωάννης Μούρτος, Αναπληρωτής Καθηγητής, Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας, Οικονομικό Πανεπιστήμιο Αθηνών
Ευάγγελος Ράπτης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Πρωτότυπος Τίτλος:
Cyclability: Combinatorial Properties, Algorithms and Complexity
Γλώσσες διατριβής:
Αγγλικά
Μεταφρασμένος τίτλος:
Κυκλωσιμότητα: Συνδυαστικές Ιδιότητες, Αλγόριθμοι και Πολυπλοκότητα
Περίληψη:
Ένα γράφημα G καλείται k-κυκλώσιμο, αν για κάθε k από τις κορυφές του υπάρχει ένας κύκλος στο G που τις περιέχει. Η κυκλωσιμότητα ενός γραφήματος G είναι ο μέγιστος ακέραιος k για τον οποίο το G είναι k-κυκλώσιμο και είναι μία παράμετρος που σχετίζεται με τη συνεκτικότητα. Σε αυτή τη διδακτορική διατριβή μελετάμε, κυρίως από τη σκοπιά της Παραμετρικής Πολυπλοκότητας, το πρόβλημα ΚΥΚΛΩΣΙΜΟΤΗΤΑ: Δεδομένου ενός γραφήματος G = (V,E) και ενός μη αρνητικού ακεραίου k (η παράμετρος), να αποφασιστεί αν η κυκλωσιμότητα του G είναι ίση με k.
Το πρώτο μας αποτέλεσμα είναι αρνητικό και δείχνει ότι η ύπαρξη ενός FPT-αλγορίθμου για την επίλυση του προβλήματος ΚΥΚΛΩΣΙΜΟΤΗΤΑ είναι απίθανη (εκτός αν FPT = co-
W[1], το οποίο θεωρείται απίθανο). Πιο συγκεκριμένα, αποδεικνύουμε ότι το πρόβλημα ΚΥΚΛΩΣΙΜΟΤΗΤΑ είναι co-W[1]-δύσκολο, ακόμα και αν περιορίσουμε την είσοδο στο να είναι χωριζόμενο γράφημα.
Από την άλλη, δίνουμε έναν FPT-αλγόριθμο για το ίδιο πρόβλημα περιορισμένο στην κλάση των επίπεδων γραφημάτων. Για να το πετύχουμε αυτό αποδεικνύουμε μια σειρά από συνδυαστικά αποτελέσματα σχετικά με την κυκλωσιμότητα και εφαρμόζουμε μια εκδοχή δύο βημάτων της περίφημης τεχνικής της άσχετης κορυφής, που εισήχθη από τους Robertson και Seymour στη σειρά εργασιών τους για Ελλάσονα Γραφήματα, ως ένα κρίσιμο συστατικό του αλγορίθμου τους για την επίλυση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ. Για να αποδείξουμε την ορθότητα του αλγορίθμου μας εισάγουμε έννοιες, όπως αυτή των ζωτικών κυκλικών συνδέσμων, και αποδεικνύουμε αποτελέσματα με ανεξάρτητου γραφοθεωρητικού ενδιαφέροντος.
Κλείνουμε τη μελέτη μας με ένα δεύτερο αρνητικό αποτέλεσμα: Αποδεικνύουμε ότι για το πρόβλημα της ΚΥΚΛΩΣΙΜΟΤΗΤΑΣ δεν υπάρχουν πολυωνυμικοί πυρήνες, ακόμα και αν περιοριστούμε σε κυβικά επίπεδα γραφήματα, εκτός και αν δεν ισχύει μια υπόθεση της κλασσικής Θεωρίας Πολυπλοκότητας (ότι NP υποσύνολο του co-NP/poly).
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
κυκλωσιμότητα, παραμετρική, πολυπλοκότητα, πυρήνας, δεντροπλάτος
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
93
