National and Kapodistrian University of Athens
Παραμετρική επισκόπηση του Συνόλου Ανάδρασης Κορυφών
Abstract
dc:descriptionΣτην παρούσα εργασία μελετώνται πυρήνες και παραμετρικοί αλγόριθμοι για το πρόβλημα Σύνολο Ανάδρασης Κορυφών τόσο για κατευθυνόμενα όσο και για μη κατευθυνόμενα γραφήματα. Στο πρόβλημα αυτό σκοπός μας είναι η διαγραφή το πολύ k κορυφών ενός γραφήματος G ώστε το γράφημα που θα προκύψει να είναι άκυκλο. Το πρόβλημα αυτό είναι NP-Hard, οπότε η έρευνα έχει στραφεί σε εναλλακτικούς τρόπους για την επίλυσή του (προσεγγιστικοί αλγόριθμοι, ευριστικές μέθοδοι, κ.ά.). Ένας από τους τρόπους αυτούς είναι με παραμετρικούς αλγόριθμους, στους οποίους επικεντρώνεται η παρούσα εργασία. Στα μη κατευθυνόμενα γραφήματα υπάρχει πυρήνας μεγέθους O(k^2) για την γενική περίπτωση. Στα κατευθυνόμενα γραφήματα είναι ανοιχτό πρόβλημα η ύπαρξη πυρήνα πολυωνυμικού μεγέθους για την γενική περίπτωση, ωστόσο στην παρούσα εργασία μελετάται η περίπτωση που η παράμετρος στο πρόβλημά μας είναι το Σύνολο Ανάδρασης Κορυφών για το αντίστοιχο μη κατευθυνόμενο γραφήμα, που έχει πυρήνα μεγέθους O(k^4). Όσον αφορά τους αλγόριθμους για τα μη κατευθυνόμενα γραφήματα, κυρίως χρησιμοποιούνται συνδυαστικά επιχειρήματα για την εύρεση της πολυπλοκότητάς τους, ενώ σε μια περίπτωση χρησιμοποιήκε πρόγραμμα σε Python για κάποιους υπολογισμούς. Για τα κατευθυνόμενα γραφήματα, χρησιμοποιούνται εργαλεία της θεωρίας γραφημάτων όπως οι τομές και οι διαχωριστές ενώ χρησιμοποιούνται και κάποιες πιο αφηρημένες δομές που ονομάζονται ε-δομές για την εύρεση συνόλου ανάδρασης. Η πολυπλοκότητα των αλγορίθμων αυτών προκύπτει πάλι με συνδυαστικά επιχειρήματα. Το Σύνολο Ανάδρασης Κορυφών είναι ένα εκτενώς μελετημένο πρόβλημα στην Παραμετρική Πολυπλοκότητα με πληθώρα εφαρμογών στα Λειτουργικά Συστήματα, στην κατασκευή κυκλωμάτων VLSI αλλά και στην εύρεση γονιδίων που ευθύνονται για τον καρκίνο και ανήκει σε μια μεγαλύτερη κατηγορία προβλημάτων που αφορούν Σύνολα Ανάδρασης. Παρόμοιο πρόβλημα είναι το Σύνολο Ανάδρασης Τόξων το οποίο επίσης λύνεται με τους αλγόριθμους για το Σύνολο Ανάδρασης Κορυφών. Ο αναγνώστης αναμένεται να είναι εξοικειωμένος με βασικές έννοιες θεωρίας γραφημάτων, αλγορίθμων, υπολογιστικής και παραμετρικής πολυπλοκότητας.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Χατζηκοκολάκης Κωνσταντίνος-Νικόλαος
- Chatzikokolakis Konstantinos-Nikolaos
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:3221867