Ο φοιτητής του προγράμματος Γεώργιος Σεμερτζάκης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Extendability of Graphs with Perfect Matchings
την Τετάρτη 21 Ιουλίου 2021 και ώρα 10:30, μέσω τηλεμετάδοσης (https://us02web.zoom.us/j/88611873915?pwd=TGRoalA4S3VqR0M1ZHRLWTZnVXBJUT09).
Σύνοψη Διπλωματικής:
Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.
Η Επιτροπή,
Αρχοντία Γιαννοπούλου (Επιβλέπουσα),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτρης Ζώρος,
Εξωτερικός συνεργάτης ΑΛΜΑ
Σταύρος Κολλιόπουλος,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ