Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/31058Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Ψωμαδέλλη, Βασιλεία | el |
| dc.date.accessioned | 2021-05-27T08:20:58Z | - |
| dc.date.available | 2021-05-27T08:20:58Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/31058 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10887 | - |
| 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 | Fall coloring | en |
| dc.subject | Graph | en |
| dc.subject | Complexity | en |
| dc.subject | Algorithm | en |
| dc.title | Πτωτικός χρωματισμός σε γραφήματα | el |
| dc.title | Fall coloring of graphs | en |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Γραφήματα | - |
| heal.dateAvailable | 2021-05-27T08:21:59Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2020 | - |
| heal.bibliographicCitation | Βιβλιογραφία: 93-95 | el |
| heal.abstract | Στόχος της παρούσας διατριβής είναι η παρουσίαση και η μελέτη του προβλήματος του πτωτικού χρωματισμού σε γραφήματα. Επίσης, δίνονται και άλλα είδη χρωματισμών καθώς και η σχέση μεταξύ τους. Επιπρόσθετα, μελετάται η πολυπλοκότητα του προβλήματος του πτωτικού χρωματισμού και δίνονται κλάσεις γραφημάτων που είτε το πρόβλημα έχει πολυωνυμικό αλγόριθμο, είτε χαρακτηρίζεται ως NP – πλήρες. Παραθέτονται τα συμπεράσματα της διατριβής και σχεδιάζεται ο πρώτος πολυωνυµικός αλγόριθμος για τα cographs. Επιπλέον, μελετάται και παρουσιάζεται μια ειδική περίπτωση του προβλήματος για γενικά γραφήματα, η οποία αναφέρεται στη περίπτωση του σχεδόν – πτωτικού χρωματισμού και σχεδιάστηκε πολυωνυµικός αλγόριθμος που επιτυγχάνει κάποια αναδιάταξη της διαµέρισης, αν υπάρχει, έτσι ώστε ο συγκεκριμένος χρωματισμός να γίνεται πτωτικός χρωματισμός. | el |
| heal.abstract | The aim of this thesis is the presentation and the study of the fall coloring problem in graphs. Furthermore, different types of coloring are given and studied, as well as the relationship between them. Moreover, the complexity of the problem of fall coloring is studied and graph classes are given that either the problem has a polynomial algorithm or is characterized as NP – complete. The research findings of this thesis are presented, and the first polynomial algorithm is constructed for cographs. In addition, a polynomial algorithm is designed for the special case of fall coloring for graphs, where the graph is almost – fall coloring and it decides if there is a rearrangement of the partition classes that makes the graph fall colored. | en |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 95 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΨΩΜΑΔΕΛΛΗ ΒΑΣΙΛΕΙΑ 2020.pdf | 1.88 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
