Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΨωμαδέλλη, Βασιλείαel
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
dc.subjectΠτωτικός χρωματισμόςel
dc.subjectFall coloringen
dc.titleΠτωτικός χρωματισμός σε γραφήματαel
dc.titleFall coloring of graphsen
heal.type.enMaster thesisen
heal.type.elΜεταπτυχιακή εργασίαel
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικώνel
heal.bibliographicCitationΒιβλιογραφία: 93-95el
heal.abstractΣτόχος της παρούσας διατριβής είναι η παρουσίαση και η μελέτη του προβλήματος του πτωτικού χρωματισμού σε γραφήματα. Επίσης, δίνονται και άλλα είδη χρωματισμών καθώς και η σχέση μεταξύ τους. Επιπρόσθετα, μελετάται η πολυπλοκότητα του προβλήματος του πτωτικού χρωματισμού και δίνονται κλάσεις γραφημάτων που είτε το πρόβλημα έχει πολυωνυμικό αλγόριθμο, είτε χαρακτηρίζεται ως NP – πλήρες. Παραθέτονται τα συμπεράσματα της διατριβής και σχεδιάζεται ο πρώτος πολυωνυµικός αλγόριθμος για τα cographs. Επιπλέον, μελετάται και παρουσιάζεται μια ειδική περίπτωση του προβλήματος για γενικά γραφήματα, η οποία αναφέρεται στη περίπτωση του σχεδόν – πτωτικού χρωματισμού και σχεδιάστηκε πολυωνυµικός αλγόριθμος που επιτυγχάνει κάποια αναδιάταξη της διαµέρισης, αν υπάρχει, έτσι ώστε ο συγκεκριμένος χρωματισμός να γίνεται πτωτικός χρωματισμός.el
heal.abstractThe 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.numberOfPages95 σ.-
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΨΩΜΑΔΕΛΛΗ ΒΑΣΙΛΕΙΑ 2020.pdf1.88 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons