Algorytmy multikolorowania grafów w modelu rozproszonym

Abstract

Praca traktuje o problemie multikolorowania grafów, motywacji do rozpatrywania tego zagadnienia oraz jego zastosowaniach w metodach przydziału częstotliwości w sieciach komórkowych. Powstała na podstawie kilku prac, w których zostały przedstawione nowe algorytmy multikolorowania grafów lub lepsze oszacowania liczby multichromatycznej.Pierwszy rozdział zawiera genezę problemu. Zostały w nim opisane motywacje do rozpatrywania problemu multikolorowania grafów oraz to, jak algorytmy rozwiązujące ten problem znalazły zastosowanie w zagadnieniu przydziału częstotliwości w sieciach komórkowych, bardzo silnie rozwijającym się na przełomie tysiącleci. Drugi rozdział zawiera definicję modelu obliczeń dla algorytmów wykorzystywanych w przydziale częstotliwości w sieciach komórkowych, a więc także multikolorowania grafów heksagonalnych. Przedstawione są w nim algorytmy multikolorowania we wszystkich możliwych modelach k-lokalnych.Trzeci rozdział zawiera algorytmy multikolorowania grafów heksagonalnych bez trójkątów. Przedstawione są w nim algorytmy liniowego multikolorowania takich grafów oraz częściowe rozwiązanie najważniejszego problemu otwartego w dziedzinie multikolorowania grafów heksagonalnych, hipotezy McDiarmida-Reeda.

Phd thesis is about graph multicoloring problem, its motivation and application in frequency assignment problem in cellular network. It is based on a few papers with new graph multicoloring algorithms and new bounds for multichromatic number.The first chapter is about origin of this problem. It contains motivations for graph multicoloring problem and answer for question how we can use this algorithms in grequency assignment problem in cellular network. It is well know problem, especiallny nowadays.The second chapter contains framework description for this problem. There are also graph multicoloring algorithms in all k-local model of computation.The last chapter contain multicoloring algorithms for triangle-free hexagonal graphs. It contains linear time multicoloring algorithm and also partial solve the most important open problem in this topic: McDiarmid-Reed hipothesis.