Αλγόριθμοι και πολυπλοκότητα σε προβλήματα επεξεργασίας γραφημάτων
(EL)
Algorithms and complexity of graph modification problems
(EN)
Κωνσταντινίδης, Αθανάσιος Λ.
(EL)
Παπαδόπουλος, Χάρης
(EL)
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
Κωνσταντινίδης, Αθανάσιος Λ.
(EL)
Τα προβλήματα επεξεργασίας γραφημάτων παίζουν σημαντικό ρόλο τόσο στην δομική όσο και στην αλγοριθμική θεωρία γραφημάτων. Τα προβλήματα αυτά έχουν μελετηθεί για δεκαετίες και βρίσκουν πρακτικές εφαρμογές σε σημαντικές περιοχές έρευνας. Σε αυτήν την διατριβή μελετάμε ένα κλασικό πρόβλημα επεξεργασίας ακμών, γνωστό ως Cluster Deletion ή P_3-free Edge Deletion, και εξετάζουμε έναν κανόνα επιγραφής ακμών ο οποίος χαρακτηρίζει τα κοινωνικά δίκτυα, ως ένα πρόβλημα διαγραφής ακμών, γνωστό ως MaxSTC. Τα δύο αυτά προβλήματα είναι γνωστό ότι είναι ΝΡ-δύσκολα. Παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα για το MaxSTC και καθορίζουμε την υπολογιστική πολυπλοκότητα για το Cluster Deletion σε κλάσεις γραφημάτων. Επιπλέον, γενικεύουμε το πρόβλημα MaxSTC προτείνοντας μία "χαλάρωση1’ του κλασικού προβλήματος επεξεργασίας ακμών F-free Edge Deletion, το οποίο καλούμε Strong F-Closure. Μελετάμε το πρόβλημα Strong F-Closure από την σκοπιά της παραμετρικής πολυπλοκότητας και παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα υπό διαφορετικούς παραμέτρους.
(EL)
Graph modification problems play important role in both structural and algorithmic graph theory. These problems have been studied for decades and find a large number of practical applications in several different fields in real world. In this thesis, we study a famous edge deletion problem, known under the terms Cluster Deletion or P_3-free Edge Deletion, and we consider an edge labeling scheme that characterizes social networks in terms of an edge deletion problem, known as MaxSTC. Both problems are known to be NP-hard. We provide the first computational results of MaxSTC and we determine the computational complexity of Cluster Deletion on particular graph classes. Moreover, we generalize the MaxSTC problem and propose a relaxation of the classical F-free Edge Deletion problem that we call Strong F-Closure. We study Strong F-Closure from the parameterized perspective and provide computational results with various natural parameterizations.
(EN)
