Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/443
Title: Algorytmy multikolorowania grafów w modelu rozproszonym
Other Titles: Graph multicoloring algorithms in distributed model
Authors: Witkowski, Rafał
Advisor: Karoński, Michał. Promotor
Keywords: multikolorowanie
multicoloring
graf
graph
graf heksagonalny
hexagonal graph
sieć komórkowa
Cellular network
przydział częstotliwości
Frequency assignment
Issue Date: 11-Jun-2010
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.
Description: Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
URI: http://hdl.handle.net/10593/443
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
Witkowski_PhD.pdf3.65 MBAdobe PDFView/Open
Show full item record



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