Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/443
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKaroński, Michał. Promotor-
dc.contributor.authorWitkowski, Rafał-
dc.date.accessioned2010-06-11T09:02:26Z-
dc.date.available2010-06-11T09:02:26Z-
dc.date.issued2010-06-11T09:02:26Z-
dc.identifier.urihttp://hdl.handle.net/10593/443-
dc.descriptionWydział Matematyki i Informatyki: Zakład Matematyki Dyskretnejpl_PL
dc.description.abstractPraca 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.pl_PL
dc.description.abstractPhd 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.pl_PL
dc.language.isoplpl_PL
dc.subjectmultikolorowaniepl_PL
dc.subjectmulticoloringpl_PL
dc.subjectgrafpl_PL
dc.subjectgraphpl_PL
dc.subjectgraf heksagonalnypl_PL
dc.subjecthexagonal graphpl_PL
dc.subjectsieć komórkowapl_PL
dc.subjectCellular networkpl_PL
dc.subjectprzydział częstotliwościpl_PL
dc.subjectFrequency assignmentpl_PL
dc.titleAlgorytmy multikolorowania grafów w modelu rozproszonympl_PL
dc.title.alternativeGraph multicoloring algorithms in distributed modelpl_PL
dc.typeDysertacjapl_PL
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 simple item record



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