Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/446
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKaroński, Michał. Promotor-
dc.contributor.authorKrzywdziński, Krzysztof-
dc.date.accessioned2010-06-11T12:33:49Z-
dc.date.available2010-06-11T12:33:49Z-
dc.date.issued2010-06-11T12:33:49Z-
dc.identifier.urihttp://hdl.handle.net/10593/446-
dc.descriptionWydział Matematyki i Informatyki: Zakład Matematyki Dyskretnejpl_PL
dc.description.abstractCelem 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.pl_PL
dc.description.abstractIn the PhD thesis distributed algorithms on unit disk graphs are considered. The presented algorithms work in distributed, synchronous, message-passing model of computations. Many radio networks may be modeled by the unit disk graph. In the unit disk graph two vertices are connected by an edge if and only if their Euclidean distance is at most 1. The first algorithm finds a minimum spanning tree (MST) in the unit disk graph. The minimum spanning tree is a spanning tree with the minimum weight (minimum sum of weights of its edges). The second interesting problem is the clustering problem. In the field of distributed algorithms it is important to divide any graph into ”large” connected subgraphs (clusters) with ”small” diameter. Such division enables to solve problems locally and then apply those local results to get a global solution The third of the presented problems is called the broadcasting problem. The aim of the algorithms solving it is to disseminate a particular message from a distinguished source vertex to all other vertices in the network.pl_PL
dc.language.isoplpl_PL
dc.subjectrozproszone algorytmypl_PL
dc.subjectdistributed algorithmspl_PL
dc.subjectgrafy dyskowepl_PL
dc.subjectunit disk graphspl_PL
dc.subjectaproksymacjapl_PL
dc.subjectapproximationpl_PL
dc.subjectminimalne drzewo rozpinającepl_PL
dc.subjectminimal spanning treepl_PL
dc.subjectrozpowszechnianie informacjipl_PL
dc.subjectbroadcastingpl_PL
dc.titleRozproszone algorytmy aproksymacyjne dla grafów dyskowychpl_PL
dc.title.alternativeDistributed approximation algorithms for unit disk graphspl_PL
dc.typeDysertacjapl_PL
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
DoktoratKK-07-05-2010.pdf871.62 kBAdobe PDFView/Open
Show simple item record



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