Πτωτικός χρωματισμός σε γραφήματα
| 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.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.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία: 93-95 | el |
| heal.classification | Γραφήματα | |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.dateAvailable | 2021-05-27T08:21:59Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 95 σ. | |
| heal.publicationDate | 2020 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΨΩΜΑΔΕΛΛΗ ΒΑΣΙΛΕΙΑ 2020.pdf
- Μέγεθος:
- 1.84 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: