Rozproszone algorytmy aproksymacyjne dla grafów dyskowych
Loading...
Date
2010-06-11T12:33:49Z
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Distributed approximation algorithms for unit disk graphs
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.
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
Sponsor
Keywords
rozproszone algorytmy, distributed algorithms, grafy dyskowe, unit disk graphs, aproksymacja, approximation, minimalne drzewo rozpinające, minimal spanning tree, rozpowszechnianie informacji, broadcasting