Back to search

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 × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:3221867

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Χατζηκοκολάκης Κωνσταντίνος-Νικόλαος; Chatzikokolakis Konstantinos-Nikolaos. Παραμετρική επισκόπηση του Συνόλου Ανάδρασης Κορυφών. 2022. https://pergamos.lib.uoa.gr/uoa/dl/object/3221867