Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/449
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKaroński, Michał. Promotor-
dc.contributor.authorWawrzyniak, Wojciech-
dc.date.accessioned2010-06-14T09:53:39Z-
dc.date.available2010-06-14T09:53:39Z-
dc.date.issued2010-06-14T09:53:39Z-
dc.identifier.urihttp://hdl.handle.net/10593/449-
dc.descriptionWydział Matematyki i Informatyki: Zakład Matematyki Dyskretnejpl_PL
dc.description.abstractPrzez 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.pl_PL
dc.description.abstractOver the past several years there has been growing interest in designing distributed algorithms. It has been motivated by their practical applications in various areas of Computer Science. This thesis is devoted to deterministic distributed approximating algorithms for solving fundamental graph problems such as constructing: minimal dominating set, maximal independent set, minimum vertex cover, maximum matching and graph packing. For all algorithms I consider the synchronous, message-passing model of computations.First, in Chapter 2, we propose an algorithm solving the problem of packing a given graph H into a planar graph G. The algorithm returns an approximate solution with an approximating factor arbitrary close to one and its time complexity is of order O(logkn), where n corresponds to the number of vertices of the input graph G. It turns out that often poly-logarithmic time complexity is still unacceptable. In such situations algorithms with much worse solution, but with constant time complexity are taken into account. This issue is addressed in Chapter 3, where algorithms that produce a (2 + ε)-approximation of the minimum vertex cover problem in bounded degree graphs or graphs of bounded arboricity are presented. In the next chapter further algorithms for planar graphs with sub-logarithmic time complexity are given. They provide solutions with an (1 ± ε)-approximation factor to the following problems: the MDS, the MM and the MWIS. All these procedures terminate in log* n steps. Moreover, in the last chapter of the thesis the results are complemented with the lower bound which proves the optimality of these algorithmspl_PL
dc.language.isoplpl_PL
dc.subjectalgorytmypl_PL
dc.subjectalgorithmspl_PL
dc.subjectgrafypl_PL
dc.subjectgraphspl_PL
dc.subjectrozproszone obliczeniapl_PL
dc.subjectdistributed computingpl_PL
dc.subjectaproksymacjapl_PL
dc.subjectapproximationpl_PL
dc.titleRozproszone algorytmy aproksymacyjne w analizie własności grafowychpl_PL
dc.title.alternativeDistributed Approximation Algorithms in the analysis of graph propertiespl_PL
dc.typeDysertacjapl_PL
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
Wojciech Wawrzyniak-Rozprawa doktorska.pdf5.33 MBAdobe PDFView/Open
Show simple item record



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