Rozproszone algorytmy aproksymacyjne dla grafów dyskowych

Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej

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.