National Technical University of Athens (NTUA)
Αλγόριθμοι και περιπλοκότητα: χρωματισμοί γράφων και υπεργράφων
Abstract
dc:descriptionWe 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2007
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Cheilaris, Panagiotis
- Χείλαρης, Παγαγιώτης
Subjects
dc:subject × 12Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/16645