Obliczenia lokalne w grafach etykietowanych sa takimi przeksztalceniami
etykietowania grafu, w ktorych:
- zmianie ulegaja co najwyzej etykiety w obszarze lokalnosci, tj. spojnym
podgrafie o z gory wyznaczonej srednicy,
- zmiana jest dokonywana co najwyzej na podstawie wiedzy o etykietowaniu i
strukturze tegoz podgrafu.
Lokalnosc jest krotkowzroczna - swiadczy o tym istnienie grafow lokalnie
niejednoznacznych, dla ktorych nie da sie sformulowac algorytmu
rozwiazujacego jeden z rownowaznych problemow: elekcji, numeracji czy
tez znalezienia drzewa rozpinajacego. Naszym zadaniem bylo wyposazyc
lokalnosc w okulary, tj. poszukac takiego jej rozszerzenia, ktore istotnie
poprawia mozliwosci obliczeniowe protokolow, a przy tym nadal jest do
przyjecia jako dzialanie intuicujnie lokalne.
Takim rozszerzeniem okazaly sie dlugodystansowe polaczenia przekierowujace.
Dzieki ich wykorzystaniu powstal uniwersalny algorytm elekcji
dla dowolnych grafow, nie korzystajacy z jakiejkolwiek globalnej wiedzy,
tj. dzialajacy w grafach anonimowych i nie wymagajacy a priori znajomosci
ich rozmiaru. Ten algorytm zamierzamy zaprezentowac.
|
Seminaria \ Seminarium Zakładu T. P. I. \ Archiwum 2003 / 2004 \ 11.12.2003 Dobiesław Wróblewski
