Ισχυρές κλίκες σε γραφήματα
| dc.contributor.author | Ζώνιος, Ελευθέριος | el |
| dc.date.accessioned | 2021-03-10T10:26:19Z | |
| dc.date.available | 2021-03-10T10:26:19Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/30654 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10496 | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Κλίκα | el |
| dc.subject | Αλγόριθμος | el |
| dc.subject | Πολυπλοκότητα | el |
| dc.subject | Γράφημα | el |
| dc.subject | Clique | en |
| dc.subject | Algorithm | en |
| dc.subject | Complexity | en |
| dc.subject | Localizable | en |
| dc.title | Ισχυρές κλίκες σε γραφήματα | el |
| dc.title | Strong cliques in graphs | en |
| heal.abstract | Ο κεντρικός στόχος της παρούσας διατριβής είναι η παρουσίαση και η ανάλυση σε βάθος έξι προβλημάτων που σχετίζονται με ισχυρές κλίκες σε διάφορες κλάσεις γραφημάτων. Μελετάμε την υπολογιστική πολυπλοκότητα των προβλημάτων αυτών που συναντώνται στην σύγχρονη βιβλιογραφία. Πιο συγκεκριμένα, η διατριβή αποτελείται από πέντε κεφάλαια. Στο πρώτο κεφάλαιο αναφέρονται εισαγωγικές έννοιες της θεωρίας γραφημάτων και ορισμοί σχετικοί με την έννοια της υπολογιστικής πολυπλοκότητας. Στο δεύτερο κεφάλαιο δίνεται η διατύπωση των έξι προβλημάτων, καθώς, και οι εφαρμογές τους σε άλλους κλάδους των μαθηματικών και της κοινωνίας. Το τρίτο κεφάλαιο περιέχει την ανάλυση της υπολογιστικής πολυπλοκότητας των πέντε εκ των έξι προβλημάτων σε ορισμένες κλάσεις γραφημάτων. Στο τέταρτο κεφάλαιο αναλύεται η υπολογιστική πολυπλοκότητα του τελευταίου προβλήματος στις κλάσεις γραφημάτων του τρίτου κεφαλαίου, συμπεριλαμβανομένου ενός αλγορίθμου που λύνει το πρόβλημα σε πολυωνυμικό χρόνο στην κλάση των cographs και την απόρριψη της εικασίας του Zaare-Nahandi μέσω αντιπαραδειγμάτων. Τέλος, στο πέμπτο κεφάλαιο παρουσιάζουμε τα συμπεράσματα αυτής της διατριβής. | el |
| heal.abstract | The main goal of this study is the presentation and in-depth analysis of six problems related to strong cliques in various classes of graphs. We study the computational complexity of these problems encountered in the modern literature. More specifically, the study consists of five chapters. In the first chapter we introduce introductory concepts of graph theory and definitions related to the concept of computational complexity. In the second chapter, we give the formulation of the six problems related to strong cliques, as well as their applications in other branches of mathematics and society. The third chapter contains the analysis of the computational complexity of five of the six problems in certain graph classes. In the fourth chapter, we analyze the computational complexity of the last problem in the graph classes of the third chapter, including an algorithm that solves the problem in polynomial time in the class cographs, and we reject the conjecture of Zaare-Nahandi by giving some counterexamples. Finally, in the fifth chapter, we present the conclusions of this study. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 83-89 | el |
| heal.classification | Αλγόριθμοι | |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.dateAvailable | 2021-03-10T10:27:19Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 89 σ. | |
| heal.publicationDate | 2020 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.secondaryTitle | αλγόριθμοι και πολυπλοκότητα σχετικών προβλημάτων | el |
| heal.secondaryTitle | algorithms and complexity of related problems | en |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΖΩΝΙΟΣ ΕΛΕΥΘΕΡΙΟΣ 2020.pdf
- Μέγεθος:
- 773.29 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: