Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/446
Title: Rozproszone algorytmy aproksymacyjne dla grafów dyskowych
Other Titles: Distributed approximation algorithms for unit disk graphs
Authors: Krzywdziński, Krzysztof
Advisor: Karoński, Michał. Promotor
Keywords: rozproszone algorytmy
distributed algorithms
grafy dyskowe
unit disk graphs
aproksymacja
approximation
minimalne drzewo rozpinające
minimal spanning tree
rozpowszechnianie informacji
broadcasting
Issue Date: 11-Jun-2010
Abstract: Celem 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.
In 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.
Description: Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
URI: http://hdl.handle.net/10593/446
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 full item record



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