Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/27802Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Κωνσταντινίδης, Αθανάσιος | el |
| dc.date.accessioned | 2017-01-27T09:13:26Z | - |
| dc.date.available | 2017-01-27T09:13:26Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/27802 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.1845 | - |
| dc.rights | An error occurred on the license name. | * |
| dc.rights.uri | An error occurred getting the license - uri. | * |
| dc.subject | Γραφήματα | el |
| dc.subject | Ισχυρή τριαδική κλειστότητα | el |
| dc.title | Αλγόριθμοι και πολυπλοκότητα της ισχυρής τριαδικής κλειστότητας σε κλάσεις γραφημάτων | el |
| dc.title | Algorithms and complexity of strong triadic closure in graph classes | en |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Αλγόριθμοι | el |
| heal.classification | Γραφήματα (Μαθηματικά) | el |
| heal.dateAvailable | 2017-01-27T09:14:26Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2016 | - |
| heal.bibliographicCitation | Βιβλιογραφία : σ. 49-51 | el |
| heal.abstract | Στα κοινωνικά δίκτυα η Ισχυρη Τριαδικη κλειστοτητα είναι µία ανάθεση στις ακµές µε ισχυρές ή ασθενείς επιγραφές, τέτοια ώστε για δύο οποιεσδήποτε κορυ- φές που έχουν κοινό γείτονα µε ισχυρή ακµή να είναι γειτονικές. Το πρόβληµα της µεγιστοποίησης των ισχυρών ακµών, οι οποίες ικανοποιούν την ισχυρή τριαδική κλειστότητα, έχει πρόσφατα αποδειχτεί ότι είναι NP-πλήρες σε γενικά γραφήµατα. Στην παρούσα διατριβή γίνεται µελέτη σε κλάσεις γραφηµάτων, για τις οποίες το πρόβληµα χαρακτηρίζεται είτε µε πολυωνυµική λύση είτε παραµένει NP-πλήρες. 6είχνουµε ότι το πρόβληµα δέχεται πολυωνυµικό σε χρόνο αλγόριθµο σε δύο ανεξάρτητες κλάσεις γραφηµάτων των proper interval και των trivially-perfect, καθώς και στις κλάσεις των bipartite, co-bipartite και threshold γραφηµάτων. Για να έχουµε µια πιο κατηγοριοποιηµένη και ολοκληρωµένη αντίληψη των α- ποτελεσµάτων µας, δείχνουµε ότι το πρόβληµα παραµένει NP-πλήρες στα split γραφήµατα, και ακολούθως στα chordal γραφήµατα. Εποµένως, µέσα από την διατριβή αυτή συµβάλουµε να οριστούν τα πρώτα διαχωριστικά όρια µεταξύ των κλάσεων γραφηµάτων, όπου σε κάποιες κλάσεις το πρόβληµα λύνεται σε πολυω- νυµικό χρόνο ενώ σε άλλες κλάσεις το πρόβληµα παραµένει NP-πλήρες. | el |
| heal.abstract | In social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. In this thesis we initiate the study of graph classes for which the problem is either polynomially solvable or remains NP-complete. We show that the problem admits a polynomialtime algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs, as well as, on classes of bipartite graphs, cobipartite graphs and threshold graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus in this thesis we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete. | en |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Νικολόπουλος, Σταύρος | el |
| heal.committeeMemberName | Γλυνός, Νικόλαος | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 51 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΚΩΝΣΤΑΝΤΙΝΙΔΗΣ ΑΘΑΝΑΣΙΟΣ 2016.pdf | 674.19 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
