Abstrakt
Idea algorytmów samostabilizujących została zapoczątkowana przez E. Dijkstrę artykułem pt. „Self-stabilizing systems in spite of distributed control” (Communications of the ACM, 1974). W rozprawie został położony nacisk na algorytmy samostabilizujące działające w sieciach o pewnych specyficznych topologiach, jak na przykład w grafach maksymalnych zewnętrznie planarnych, iloczynach kartezjańskich tych grafów ze ścieżkami i w drzewach. Wykorzystując powyższe własności sieci, pokazaliśmy algorytmy, które działają efektywniej w porównaniu ze znanymi obecnie algorytmami samostabilizującymi dla ogólnych topologii sieci. Ponadto pokazaliśmy algorytm wyznaczający zbiór cykli fundamentalnych grafu, należący do zaproponowanej przez nas klasy algorytmów quasi-samostabilizujących. Jest to rozszerzenie idei zaproponowanej przez Schneidera w artykule „Self-Stabilization” (ACM Computing Surveys, 1993). Dzięki temu nasz algorytm ma mniejszą złożoność w stosunku do klasycznego wyniku samostabilizującego.
Autor (1)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
- Copyright (Author(s))
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Doktoraty, rozprawy habilitacyjne, nostryfikacje
- Typ:
- praca doktorska pracowników zatrudnionych w PG oraz studentów studium doktoranckiego
- Język:
- polski
- Rok wydania:
- 2016
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 73 razy