1. Repository of OAI
  2. ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"
  3. Σχολή Θετικών Επιστημών
  4. Τμήμα Μαθηματικών
  5. Διδακτορικές Διατριβές - ΜΑΘ
Ελληνικά   English  
Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/31286
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΚωνσταντινίδης, Αθανάσιος Λ.el
dc.date.accessioned2021-08-25T06:59:26Z-
dc.date.available2021-08-25T06:59:26Z-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/31286-
dc.identifier.urihttp://dx.doi.org/10.26268/heal.uoi.11111-
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
dc.subjectGraph theoryen
dc.subjectGraph modification problemsen
dc.subjectComplexityen
dc.subjectParameterized complexityen
dc.subjectAlgorithmsen
dc.subjectStrong triadic closureen
dc.subjectCluster deletionen
dc.subjectΘεωρία γραφημάτωνel
dc.subjectΠροβλήματα επεξεργασίας γραφημάτωνel
dc.subjectΠολυπλοκότηταel
dc.subjectΠαραμετρική πολυπλοκότηταel
dc.subjectΑλγόριθμοιel
dc.subjectΙσχυρή τριαδική κλειστότηταel
dc.titleAlgorithms and complexity of graph modification problemsen
dc.titleΑλγόριθμοι και πολυπλοκότητα σε προβλήματα επεξεργασίας γραφημάτωνel
heal.typedoctoralThesis-
heal.type.enDoctoral thesisen
heal.type.elΔιδακτορική διατριβήel
heal.classificationGraph theory-
heal.dateAvailable2021-08-25T07:00:27Z-
heal.languageen-
heal.accessfree-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικώνel
heal.publicationDate2021-
heal.bibliographicCitationΒιβλιογραφία: σ. 141-150el
heal.abstractGraph 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
heal.abstractΤα προβλήματα επεξεργασίας γραφημάτων παίζουν σημαντικό ρόλο τόσο στην δομική όσο και στην αλγοριθμική θεωρία γραφημάτων. Τα προβλήματα αυτά έχουν μελετηθεί για δεκαετίες και βρίσκουν πρακτικές εφαρμογές σε σημαντικές περιοχές έρευνας. Σε αυτήν την διατριβή μελετάμε ένα κλασικό πρόβλημα επεξεργασίας ακμών, γνωστό ως Cluster Deletion ή P_3-free Edge Deletion, και εξετάζουμε έναν κανόνα επιγραφής ακμών ο οποίος χαρακτηρίζει τα κοινωνικά δίκτυα, ως ένα πρόβλημα διαγραφής ακμών, γνωστό ως MaxSTC. Τα δύο αυτά προβλήματα είναι γνωστό ότι είναι ΝΡ-δύσκολα. Παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα για το MaxSTC και καθορίζουμε την υπολογιστική πολυπλοκότητα για το Cluster Deletion σε κλάσεις γραφημάτων. Επιπλέον, γενικεύουμε το πρόβλημα MaxSTC προτείνοντας μία "χαλάρωση1’ του κλασικού προβλήματος επεξεργασίας ακμών F-free Edge Deletion, το οποίο καλούμε Strong F-Closure. Μελετάμε το πρόβλημα Strong F-Closure από την σκοπιά της παραμετρικής πολυπλοκότητας και παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα υπό διαφορετικούς παραμέτρους.el
heal.advisorNameΠαπαδόπουλος, Χάρηςel
heal.committeeMemberNameΠαπαδόπουλος, Χάρηςel
heal.committeeMemberNameΝικολόπουλος, Σταύρος Δ.el
heal.committeeMemberNameΠαληός, Λεωνίδαςel
heal.committeeMemberNameΓεωργιάδης, Λουκάςel
heal.committeeMemberNameΖαρολιάγκης, Χρήστοςel
heal.committeeMemberNameΘηλυκός, Δημήτριοςel
heal.committeeMemberNameΘηλυκός, Δημήτριοςel
heal.committeeMemberNameΝομικός, Χρήστοςel
heal.academicPublisherΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικώνel
heal.academicPublisherIDuoi-
heal.numberOfPages170 σ.-
heal.fullTextAvailabilitytrue-
Appears in Collections:Διδακτορικές Διατριβές - ΜΑΘ

Show simple item record
Files in This Item:
File Description SizeFormat 
Δ.Δ. ΚΩΝΣΤΑΝΤΙΝΙΔΗΣ ΑΘΑΝΑΣΙΟΣ Ι. 2021.pdf1.46 MBAdobe PDFView/Open
Show simple item record  


This item is licensed under a Creative Commons License Creative Commons