Αλγόριθμοι και πολυπλοκότητα της ισχυρής τριαδικής κλειστότητας σε κλάσεις γραφημάτων
| 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.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.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία : σ. 49-51 | el |
| heal.classification | Αλγόριθμοι | el |
| heal.classification | Γραφήματα (Μαθηματικά) | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Νικολόπουλος, Σταύρος | el |
| heal.committeeMemberName | Γλυνός, Νικόλαος | el |
| heal.dateAvailable | 2017-01-27T09:14:26Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 51 σ. | |
| heal.publicationDate | 2016 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΚΩΝΣΤΑΝΤΙΝΙΔΗΣ ΑΘΑΝΑΣΙΟΣ 2016.pdf
- Μέγεθος:
- 674.19 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: