Πτωτικός χρωματισμός σε γραφήματα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Ψωμαδέλλη, Βασιλεία
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Στόχος της παρούσας διατριβής είναι η παρουσίαση και η μελέτη του προβλήματος του πτωτικού χρωματισμού σε γραφήματα. Επίσης, δίνονται και άλλα είδη χρωματισμών καθώς και η σχέση μεταξύ τους. Επιπρόσθετα, μελετάται η πολυπλοκότητα του προβλήματος του πτωτικού χρωματισμού και δίνονται κλάσεις γραφημάτων που είτε το πρόβλημα έχει πολυωνυμικό αλγόριθμο, είτε χαρακτηρίζεται ως NP – πλήρες. Παραθέτονται τα συμπεράσματα της διατριβής και σχεδιάζεται ο πρώτος πολυωνυµικός αλγόριθμος για τα cographs. Επιπλέον, μελετάται και παρουσιάζεται μια ειδική περίπτωση του προβλήματος για γενικά γραφήματα, η οποία αναφέρεται στη περίπτωση του σχεδόν – πτωτικού χρωματισμού και σχεδιάστηκε πολυωνυµικός αλγόριθμος που επιτυγχάνει κάποια αναδιάταξη της διαµέρισης, αν υπάρχει, έτσι ώστε ο συγκεκριμένος χρωματισμός να γίνεται πτωτικός χρωματισμός.
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.
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.
Περιγραφή
Λέξεις-κλειδιά
Πτωτικός χρωματισμός, Γραφήματα, Πολυπλοκότητα, Αλγόριθμος, Fall coloring, Graph, Complexity, Algorithm
Θεματική κατηγορία
Γραφήματα
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Παπαδόπουλος, Χάρης
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: 93-95
Ονόματα συντελεστών
Αριθμός σελίδων
95 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States