Browsing by Author "Karoński, Michał. Promotor"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
- ItemAlgorytmy multikolorowania grafów w modelu rozproszonym(2010-06-11T09:02:26Z) Witkowski, Rafał; Karoński, Michał. PromotorPraca 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.
- ItemMetody Algorytmiczne w Badaniach Siły Nieregularności Grafów(2010-06-11T12:13:03Z) Kalkowski, Maciej; Karoński, Michał. PromotorCelem rozprawy jest przedstawienie nowych metod rozwiązywania problemów globalnej i lokalnej siły nieregularności grafów. Powyższe dwa zagadnienia są rozpatrzone zarówno dla grafów ważonych, jak i totalnie ważonych. Wszystkie przedstawione metody i dowody mają charakter algorytmów wyznaczających wartości funkcji ważących. Rozdział drugi składa się z dwóch części i dotyczy lokalnego rozróżniania wierzchołków. W pierwszej, zagadnienie omówione jest dla totalnego ważenia. Wprowadzone są dwa twierdzenia, dowodzące, że istnieją lokalnie nieregularne 5-totalne-ważenie oraz 3-totalne-ważenie. W drugiej części rozdziału rozważony jest problem rozróżniania wierzchołków dla ważenia krawędzi nawiązujący do hipotezy 1-2-3. Wprowadzone są trzy nowe metody rozwiązania problemu, które wykazują, że możliwe są konstrukcje lokalnie nieregularnych 10-ważenia, 6-ważenia i 5-ważenia grafu. Rozdział trzeci dotyczy globalnego rozróżniania wierzchołków i również składa się z dwóch części. W pierwszej, zagadnienie rozpatrzone jest dla ważenia krawędzi grafu. Opisana jest metoda konstrukcji globalnie nieregularnego 6 ⌈n/δ⌉ -ważenia grafu. W drugiej części rozdziału omówione jest globalne rozróżnianie wierzchołków dla totalnego ważenia grafów. Wykazana jest konstrukcja globalnie nieregularnego (3⌈n/δ ⌉+1)-totalnego-ważenia. W ostatnim rozdziale przedstawione są pokrewne problemy rozróżniania wierzchołków.
- ItemRozproszone algorytmy aproksymacyjne dla grafów dyskowych(2010-06-11T12:33:49Z) Krzywdziński, Krzysztof; Karoński, Michał. PromotorCelem rozprawy jest przedstawienie szybkich algorytmów aproksymacyjnych rozwiązujących w modelu rozproszonym niektóre z istotnych ze względu na zastosowania problemów. Rozważania skupiają się na zagadnieniach związanych z sieciami zdecentralizowanymi, w których komunikacja odbywa się drogą radiową. Ich teoretycznym modelem są jednostkowe grafy dyskowe, w których wierzchołki są punktami na płaszczyźnie a połączenia powstają między wierzchołkami w odległości co najwyżej 1. Rozważania dotyczyć będą trzech istotnych klas problemów związanych z działaniem i strukturą sieci radiowych. Pierwszą z nich są zagadnienia związane ze znalezieniem optymalnej struktury komunikacyjnej i z bezkolizyjnym rozsyłaniem informacji. Przedstawiony jest algorytm konstruujący aproksymację minimalnego drzewa rozpinającego, czyli strukturę minimalizującą sumaryczny koszt rozesłania informacji w całej sieci. Kolejnym z problemów jest konstrukcja podziału grafu na klastry (fragmenty). Rozważamy także zagadnienie kolorowania i związany z nim problem przydziału częstotliwości w sieciach radiowych.
- ItemRozproszone algorytmy aproksymacyjne w analizie własności grafowych(2010-06-14T09:53:39Z) Wawrzyniak, Wojciech; Karoński, Michał. PromotorPrzez ostatnie kilkanaście lat zauważyć można znaczący wzrost zainteresowania algorytmami rozproszonymi. Powodem jest zastosowanie ich w wielu praktycznych zagadnieniach informatyki. Celem rozprawy doktorskiej jest przedstawienie i omówienie deterministycznych rozproszonych algorytmów aproksymacyjnych rozwiązujących podstawowe problemy grafowe, takie jak konstrukcja: minimalnego zbioru dominującego, największego zbioru niezależnego, minimalnego pokrycia wierzchołkowego, największego skojarzenia oraz pakowania grafów. Modelem obliczeń przeze mnie rozważanym jest tzw. model Local. W Rozdziale 2 opisany jest algorytm rozwiązujący problem pakowania grafu G=(V,E) w planarnym grafie H. Zwracane rozwiązanie jest dowolnie dobrą aproksymacją problemu, a złożoność czasowa algorytmu wynosi O(logk|V|). Z praktycznego punktu widzenia zastosowanie znajdują również algorytmy działające w znacząco krótszym czasie, jednak o dużo gorszym współczynniku aproksymacji. Podejście to przedstawiono w Rozdziale 3, gdzie opisane zostały algorytmy działające w czasie O(1). Konstruują one (2 + ε)-aproksymację minimalnego pokrycia wierzchołkowego, w grafach o ograniczonym stopniu, o ograniczonej lesistości. W Rozdziale 4 opisane zostały algorytmy działające w czasie O(log*n). Zwracają one przybliżone rozwiązanie problemów: minimalnego zbioru dominującego, największego skojarzenia oraz największego ważonego zbioru niezależnego w grafach planarnych. Współczynnik aproksymacji wynosi (1 ± ε). Ponadto z twierdzenia udowodnionego w ostatnim Rozdziale 5 wynika, że algorytmy te są optymalne.
- ItemSiła nieregularności grafów(2010-12-28T14:07:09Z) Anholcer, Marcin; Karoński, Michał. PromotorJednym z lepiej znanych faktów na temat grafów prostych jest to, że każdy z nich posiada co najmniej dwa wierzchołki tego samego stopnia (fakt ten wynika z zasady szufladkowej).Sytuacja zmienia się, gdy przypisujemy wagi (będące liczbami naturalnymi) krawędziom, bądź krawędziom i wierzchołkom G i rozważamy ważone stopnie wierzchołków zamiast zwykłych. W pracy rozważane są trzy parametry: siła nieregularności s(G), totalna wierzchołkowa siła nieregularności tvs(G) i iloczynowa siła nieregularności ps(G).W pierwszym rozdziale pracy zostały podane górne ograniczenia na tvs(G) dla dowolnego grafu G. Autor przedstawia również dokładne wartości tvs(F), gdzie F jest lasem nie posiadającym wierzchołków stopnia 2, i tvs(Cnk), gdzie Cnk jest k-tą potęgą cyklu Cn.Drugi rozdział zawiera rezultaty na temat siły nieregularności, s(G). W szczególności, wyznaczono dokładną wartość s(Cnk).W ostatnim rozdziale przedstawione zostały fakty na temat iloczynowej siły nieregularności. Głównymi rezultatami są górne ograniczenia na ps(G), gdzie G jest cyklem albo kratą o wystarczająco wielu wierzchołkach.