Algorytmy multikolorowania grafów w modelu rozproszonym

Loading...
Thumbnail Image

Date

2010-06-11T09:02:26Z

Editor

Journal Title

Journal ISSN

Volume Title

Publisher

Title alternative

Graph multicoloring algorithms in distributed model

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

Sponsor

Keywords

multikolorowanie, multicoloring, graf, graph, graf heksagonalny, hexagonal graph, sieć komórkowa, Cellular network, przydział częstotliwości, Frequency assignment

Citation

Seria

ISBN

ISSN

DOI

Title Alternative

Rights Creative Commons

Creative Commons License

Uniwersytet im. Adama Mickiewicza w Poznaniu
Biblioteka Uniwersytetu im. Adama Mickiewicza w Poznaniu
Ministerstwo Nauki i Szkolnictwa Wyższego