Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8648
Title: Αλγόριθμοι Και Πολυπλοκότητα: Χρωματισμοί Γράφων Και Υπεργράφων
Authors: Παναγιώτης Χείλαρης
Ζάχος Ευστάθιος
Keywords: γράφος υπεργράφος χρωματισμός αλγόριθμος άμεσος
Issue Date: 9-Jun-2008
Abstract: Μελετάμε διάφορους χρωματισμούς κορυφών για γράφους και υπεργράφους. Επικεντρωνόμαστε στους χρωματισμούς χωρίς συγκρούσεις. Οι χρωματισμοί χωρίς συγκρούσεις έχουν εφαρμογές στην αποδοτική ανάθεση συχνοτήτων σε κυψελωτά δίκτυα. Δείχνουμε πώς σχετίζονται οι χρωματισμοί χωρίς συγκρούσεις ως προς μονοπάτια γράφων με άλλα προβλήματα χρωματισμού γράφων, όπως: διατεταγμένοι χρωματισμοί (ή αλλιώς κατάταξη κορυφών), χρωματισμοί χωρίς τετράγωνα (συμβολοσειρές), και κλασικοί χρωματισμοί γράφων. Αποδεικνύουμε ιδιότητες των παραπάνω χρωματισμών καθώς και άνω και κάτω φράγματα για τα χρώματα που απαιτούνται για διάφορες κλάσεις γράφων (αλυσίδες, δακτύλιοι, δένδρα, πλέγματα).Αναλύουμε διάφορες εκδοχές του χρωματισμού χωρίς συγκρούσεις για γράφους αλυσίδες και γράφους δακτυλίους ως προς μονοπάτια. Στην περίπτωση των αλυσίδων το πρόβλημα είναι επίσης γνωστό ως χρωματισμός χωρίς συγκρούσεις ως προς διαστήματα. Για μία άμεση (online) εκδοχή του προβλήματος όπου οι κορυφές του γράφου εμφανίζονται μία μία και ο αλγόριθμος πρέπει να δεσμευτεί στο χρώμα της κορυφής προτού δει τις θέσεις των μελλοντικών κορυφών, αναλύουμε τον άπληστο αλγόριθμο πρώτου ταιριάσματος και τον άπληστο αλγόριθμο μοναδικού μεγίστου. Αποδεικνύουμε ακριβώς πόσα χρώματα χρησιμοποιεί ο άπληστος αλγόριθμος πρώτου ταιριάσματος στην χειρότερη περίπτωση και αναλύουμε ειδικές εισόδους για τον άπληστο αλγόριθμο μοναδικού μεγίστου. Επίσης, συσχετίζουμε χρωματισμούς μοναδικού μεγίστου όπου το χρώμα «1» εμφανίζεται i φορές με μεταθέσεις με i-1 κοιλάδες. Ένα ουσιώδες μέρος της ανάλυσής μας βασίζεται στον αριθμό των χρωμάτων που εμφανίζονται μόνον μία φορά (στον εκάστοτε χρωματισμό). Τέλος, ορίζουμε δύο νέα μοντέλα άμεσων αλγορίθμων χρωματισμών χωρίς συγκρούσεις ως προς διαστήματα: ένα αιτιοκρατικό στο οποίο ο αλγόριθμός γνωρίζει τις απόλυτες τελικές θέσεις των προς χρωματισμό κορυφών, και ένα πιθανοκρατικό στο οποίο ο αντίπαλος του αλγορίθμου πρέπει να δεσμευτεί στην είσοδο του πριν ο αλγόριθμος αρχίσει να χρωματίζει. Για αυτά τα δύο μοντέλα δίνουμε αλγορίθμους που χρησιμοποιούν λογαριθμικό αριθμό χρωμάτων.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8648
Appears in Collections:Διδακτορικές Διατριβές - Ph.D. Theses

Files in This Item:
File SizeFormat 
PD2008-0022.pdf658.45 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.