Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs

Διπλωματική Εργασία uoadl:2865406 316 Αναγνώσεις

Μονάδα:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)
Πληροφορική
Ημερομηνία κατάθεσης:
2019-03-07
Έτος εκπόνησης:
2019
Συγγραφέας:
Σταμούλης Γιάννος
Στοιχεία επιβλεπόντων καθηγητών:
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Αποσυνθέσεις και Αλγόριθμοι για το πρόβλημα των Διακεκριμένων Μονοπατιών σε Επίπεδα Γραφήματα
Περίληψη:
Στο πρόβλημα των Διακεκριμενων Μονοπατιων μας ζητείται να εξετάσουμε, δεδομένου ενός γραφήματος G και ενος συνόλου k ζευγών τερματικών,αν τα ζεύγη των τερματικών μπορούν να συνδεθούν με διακεκριμένα μονοπάτια. Στα "Graph Minors", μια σειρά 23 εργασιών μεταξύ 1984 και 2011, οι Neil Robertson και Paul D. Seymour, ανάμεσα σε άλλα σπουδαία αποτελέσματα που επηρέασαν βαθιά την Θεωρία Γραφημάτων, παρουσίασαν έναν f(k)*n^3 αλγόριθμο για το πρόβλημα των Διακεκριμενων Μονοπατιων. Για να το καταφέρουν αυτό, εισήγαγαν την "τεχνκή της άσχετης κορυφής" σύμφωνα με την οποία σε κάθε στιγμιότυπο δεντροπλάτους μεγαλύτερου του g(k) υπάρχει μια "άσχετη" κορυφή της οποίας η αφαίρεση δημιουργεί ένα ισοδύναμο στιγμιότυπο του προβλήματος.
Εδώ μελετάμε το πρόβλημα σε επίπεδα γραφήματα και αποδεικνύουμε ότι για κάθε σταθερό k κάθε στιγμιότυπο του προβλήματος των Διακεκριμενων Μονοπατιων σε επιπεδα γραφηματα μπορεί να μετασχηματιστεί σε ένα ισοδύναμο που έχει φραγμένο δενδροπλάτος, αφαιρώντας ταυτόχρονα ένα σύνολο κορυφών από το δεδομένο επίπεδο γράφημα. Ως συνέπεια αυτού, το πρόβλημα των Διακεκριμένων Μονοπατιών σε επίπεδα γραφήματα μπορεί να λυθεί σε γραμμικό χρόνο για κάθε σταθερό πλήθος τερματικών.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
παραμετρικοί αλγόριθμοι, παραμετρική πολυπλοκότητα, πρόβλημα διακεκριμένων μονοπατιών, δεσμώσεις, τεχνική άσχετης κορυφής, δεντροπλάτος
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
1
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
35
Αριθμός σελίδων:
38