Kolorowanie drzewa ukorzenionego, alg Cole & Vishkin i jego uogólnienie¶
model synch, algorytm działa w czasie O(log ^*n)...
początkowy kolor wierz to ID wierz, końcowy kolor jest zapisany na 3 bitach (stąd 8 kolorów !!)
wyjaśnienie dlaczego algorytm produkuje prawidłowe kolorowanie wierz:¶
v, pv = parent v, ppv = parent pv
pokazujemy, że C_v i C_pv muszą być różne, po obliczeniu nowego koloru, dla dowolnego v...
uogólnienie do dowolnych grafów: (Delta+1)- kolorowanie wierz w czasie O(Delta^2 + log ^*n)¶
dodatkowe objaśnienia do powyższego algorytmu:
czas 2-kolorowanie a 3-kolorowania cyklu - tzw. dolne oszacowania¶
Okazuje się, że jest duża różnica:
- 2-kol wymaga czasu rzędu "n"
- 3-kol (lub 300-kol) da się zrobić w czasie O(log^*n) i NIE da się zrobić w stałym czasie(!)
dowód 1.
Zakładamy, że istnieje alg A obl. 2-kol-wierz cyklu w czasie T < n/5;
alg ten musi działać w każdym cyklu (z dowolnymi ID wierz);
w czasie T każdy wierz v „widzi” ID wierz w odległości <= T od v,
i na tej podstawie oblicza swój kolor, dotyczy to wierz a i b ...
Alg A powinien działać (obl 2-kol-wierz) dla cyklu z dowolnymi ID...
Alg A działa dla lewego cyklu; tworzymy prawy cykl i alg A powinien nadal działać...
Jednak wierz a i b widzą to samo, czyli obl ten sam kolor w prawym cyklu!!!
a to nie jest PRAWIDŁOWE 2-kol-wierz... SPRZECZNOŚĆ!!
dowód 2.
to, że "da się" wynika z zadania 21; ale dlaczego nie można szybciej np. w stałym czasie???
patrz dowód, oparty na Tw Ramseya, że nie da się obl stałej aproks MIS w cyklu, w stałym czasie;
zauważmy, że gdyby można było obl 3-kol-wierz w stałym czasie, to to by zaprzeczało powyższemu dowodowi...
(terminologia: "MIS maximal" maks w sensie zawierania, "MIS maximum" maks mocy)
Zadania¶
ZADANIE 20 "impl C&V dla drzewa ukorzenionego"
zaimplementuj podstawowy algorytm;
przydatne procedury j. Tcl są tutaj;
dodatkowo postaraj się uzyskać mniej kolorów (3 a nie 8);
zwróć uwagę, że korzeń nie ma "parenta"!
ZADANIE 21 (2pkt) "3-kolorowanie cyklu niezorientowanego"
wykorzystaj technikę C&V dla drzew ukorzenionych
aby obliczyć 3-kol-wierz cyklu...
ZADANIE 22 (2pkt) "kolorowanie drzewa 2-zorientowanego"
drzewo 2-zorient to takie, w którym z każdego wierz wystają <=2 strzałki;
należy opracować alg obliczający O(1)-kol-wierz, w czasie O(log^*n);
wskazówka: raczej powinno to być uogólnienie pierwotnego alg C&V dla drzew ukorz.
ZADANIE 23 "obliczanie 2-orientacji drzewa"
dane jest drzewo; oblicz jego 2-orientacje (z każdego wierz wychodzą <=2 strzałki);
pomoce: gen drzewa losowego: drzewolosowe01.c, DodajKraw
ZADANIE 24 "postać kanoniczna alg C&V"
postać "kanoniczna" to taka w której: 1) zbieramy dane, 2) wykonujemy obliczenia (bez komunikacji);
należy opracować alg C&V w postaci kanonicznej, dla drzewa ukorzenionego;
motywacja: obliczenia na GPU... np. bibl OpenCL; GPU-efektywność algorytmu ?!?!
graf w pamięci globalnej, 1 wątek GPU = 1 wierz,
najpierw ściąganie danych z pamięci globalnej, potem obliczenia na zm. lokalnych...
alternatywna wersja zadania: zrobić impl C&V używając bibl OpenCL, w j. C
lub w nakładce skryptowej na OpenCL...
porównać z impl. 1-wątkową w j. C na CPU !!