Μονάδα:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Ημερομηνία κατάθεσης:
2021-07-27
Συγγραφέας:
Σεμερτζάκης Γεώργιος
Στοιχεία επιβλεπόντων καθηγητών:
Αρχοντία Γιαννοπούλου, Επίκουρη Καθηγήτρια, Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ε.Κ.Π.Α.
Πρωτότυπος Τίτλος:
Extendability of Graphs with Perfect Matchings
Γλώσσες εργασίας:
Αγγλικά
Ελληνικά
Μεταφρασμένος τίτλος:
Επεκτασιμότητα Γραφημάτων με Τέλεια Ταιριάσματα
Περίληψη:
Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M;
Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger.
Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
επεκτασιμότητα, τέλειο ταίριασμα, διμερές, εναλλασσόμενα μονοπάτια, πολυπλοκότητα
Αρ. σελίδων ευρετηρίου:
1
Αρ. βιβλιογραφικών αναφορών:
15
