Αλγόριθμοι και περιπλοκότητα: χρωματισμοί γράφων και υπεργράφων

Abstract

We study several vertex coloring problems for graphs and hypergraphs. We concentrate on conflict-free coloring. The conflict-free coloring problem has applications in efficient frequency assignment in cellular networks. We show the relation of conflict-free coloring paths of graphs with other graph coloring problems, like ordered coloring (also known as vertex ranking), square free coloring, and traditional graph coloring. We prove properties of the above colorings and upper and lower bounds for the colors needed for several graph classes (chains, rings, trees, grids). We analyze several versions of conflict-free coloring chain and ring graphs with respect to paths. For chain graphs, the problem is also known as conflict- free coloring with respect to intervals. For an online version of the problem where vertices of the graph appear one by one, and an algorithm has to commit on the color of a vertex before seeing the positions of the future vertices, we analyze the first-fit greedy and the unique maximum greedy algorithms. We prove tights bounds for the colors used by the first-fit greedy algorithm and we analyze special input sequences for the unique maximum greedy algorithm. We also relate unique maximum colorings with i occurrences of color ‘1’ with permutations with i — 1 valleys. An essential part of the analysis is based on counting the number of uniquely occurring colors. Finally, we define two new online algorithm models for conflict-free coloring with respect to intervals: one is deterministic and the algorithm has knowledge of the absolute final positions of the vertices to be colored, and the other is probabilistic and the adversary has to commit to the input before the algorithm starts coloring. For these two models, we provide algorithms that use a logarithmic number of colors.

Μελετάμε διάφορους χρωματισμούς κορυφών για γράφους και υπεργράφους. Επικεντρωνόμαστε στους χρωματισμούς χωρίς συγκρούσεις. Οι χρωματισμοί χωρίς συγκρούσεις έχουν εφαρμογές στην αποδοτική ανάθεση συχνοτήτων σε κυψελωτά δίκτυα. Δείχνουμε πώς σχετίζονται οι χρωματισμοί χωρίς συγκρούσεις ως προς μονοπάτια γράφων με άλλα προβλήματα χρωματισμού γράφων, όπως: διατεταγμένοι χρωματισμοί (ή αλλιώς κατάταξη κορυφών), χρωματισμοί χωρίς τετράγωνα (συμβολοσειρές), και κλασικοί χρωματισμοί γράφων. Αποδεικνύουμε ιδιότητες των παραπάνω χρωματισμών καθώς και άνω και κάτω φράγματα για τα χρώματα που απαιτούνται για διάφορες κλάσεις γράφων (αλυσίδες, δακτύλιοι, δένδρα, πλέγματα). Αναλύουμε διάφορες εκδοχές του χρωματισμού χωρίς συγκρούσεις για γράφους αλυσίδες και γράφους δακτυλίους ως προς μονοπάτια. Στην περίπτωση των αλυσίδων το πρόβλημα είναι επίσης γνωστό ως χρωματισμός χωρίς συγκρούσεις ως προς διαστήματα. Για μία άμεση (online) εκδοχή του προβλήματος όπου οι κορυφές του γράφου εμφανίζονται μία μία και ο αλγόριθμος πρέπει να δεσμευτεί στο χρώμα της κορυφής προτού δει τις θέσεις των μελλοντικών κορυφών, αναλύουμε τον άπληστο αλγόριθμο πρώτου ταιριάσματος και τον άπληστο αλγόριθμο μοναδικού μεγίστου. Αποδεικνύουμε ακριβώς πόσα χρώματα χρησιμοποιεί ο άπληστος αλγόριθμος πρώτου ταιριάσματος στην χειρότερη περίπτωση και αναλύουμε ειδικές εισόδους για τον άπληστο αλγόριθμο μοναδικού μεγίστου. Επίσης, συσχετίζουμε χρωματισμούς μοναδικού μεγίστου όπου το χρώμα «1» εμφανίζεται i φορές με μεταθέσεις με i — 1 κοιλάδες. Ένα ουσιώδες μέρος της ανάλυσής μας βασίζεται στον αριθμό των χρωμάτων που εμφανίζονται μόνον μία φορά (στον εκάστοτε χρωματισμό). Τέλος, ορίζουμε δύο νέα μοντέλα άμεσων αλγορίθμων χρωματισμών χωρίς συγκρούσεις ως προς διαστήματα: ένα αιτιοκρατικό στο οποίο ο αλγόριθμός γνωρίζει τις απόλυτες τελικές θέσεις των προς χρωματισμό κορυφών, και ένα πιθανοκρατικό στο οποίο ο αντίπαλος του αλγορίθμου πρέπει να δεσμευτεί στην είσοδο του πριν ο αλγόριθμος αρχίσει να χρωματίζει. Για αυτά τα δύο μοντέλα δίνουμε αλγορίθμους που χρησιμοποιούν λογαριθμικό αριθμό χρωμάτων.