Ο φοιτητής του προγράμματος Κωνσταντίνος-Νικόλαος Χατζηκοκολάκης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Παραμετρική επισκόπηση του Συνόλου Ανάδρασης Κορυφών
την Τρίτη 28 Ιουνίου 2022 και ώρα 11:00, στην Αίθουσα Α56 του Τμ. Πληροφορικής και Τηλεπικοινωνιών του Ε.Κ.Π.Α..
Σύνοψη Διπλωματικής:
Στην παρούσα ομιλία θα παρουσιαστεί το πρόβλημα Σύνολο Ανάδρασης Κορυφών (Feedback Vertex Set) από την σκοπιά της Παραμετρικής Πολυπλοκότητάς. Πιο συγκεκριμένα, θα παρουσιαστούν (πολυωνυμικοί) πυρήνες και παραμετρικά βατοί (FPT) αλγόριθμοι.
Όσον αφορά τους πυρήνες, θα παρουσιαστεί ένας τετραγωνικός πυρήνας για μη κατευθυνόμενα γραφήματα, και ένας πυρήνας μεγεθους O(k^4) για τα κατευθυνόμενα γραφήματα με κατάλληλη επιλογή παραμέτρων.
Επιπλέον, θα παρουσιαστούν παραμετρικά βατοί αλγόριθμοι τόσο για κατευθυνόμενα όσο και για μη κατευθυνόμενα γραφήματα.
Η Επιτροπή,
Αρχοντία Χ. Γιαννοπούλου (Επιβλέπουσα),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Βασίλειος Ζησιμόπουλος,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτρης Ζώρος,
Εξωτερικός συνεργάτης