Szybkie obliczenia w grafach planarnych (klastry)¶

grafy planarne: można narysować na płaszczyźnie bez przecinających się krawędzi;
mają ciekawe właściwości...

można "ścisnąć" kraw i znów otrzymamy graf planarny (tzn minor)
istnieje 4-kolorowanie-wierz
oraz wiele innych cech przydatnych algorytmicznie...

chcemy obliczać $(1+-\epsilon)$ -aproksymację problemów:

MM (Maximum Matching),
MDS (Minimum Dominating Set),
MIS (Maximum Independent Set);

def tych problemów, patrz:
problemy

def $(1-\epsilon)$ -aproksymacji dla problemów typu maximum:
$X$ - rozw produkowane przez algorytm,
$X^*$ - rozw optymalne,

\frac{| X |}{| X^{*} |} > 1 - ϵ

$\frac{|X|}{|X^*|} > 1-\epsilon$

Koncepcja "klastrów" ...¶

czy warto centralizować obliczenia, tzn

sciągnąć cały graf do centrum obliczeniowego,
rozwiązać problem na 1 wierz,
rozesłać rozwiązanie po całym grafie

Jest probelm: pkt 1. i 3. są bardzo czasochłonne jeśli graf ma dużą średnicę...
Rozwiązanie: klastry o małej średnicy i małym brzegu...
w każdym klastrze, równolegle i niezależnie, wykonujemy pkt 1. 2. 3.
dlaczego brzeg ma być "mały" ? aby błąd na brzegu też był mały !!
klastry ?

def klastrów:
klastry to podział zbioru wierz $V$ na podzbiory $V_1, ..., V_k$ ,
taki, że podgraf indukowany $G[V_i]$ jest spójny i ma małą (stałą) średnicę;
ponadto konektory (krawędzie miedzy klastrami), muszą mieć małą łączną wagę;
def klastrow

Mamy klastry, to jak obliczyć $(1-\epsilon)$ -aproks MWIS ?¶

MWIS to ważona wersja problemu MIS (wagi na wierz);
obl MIS
Dlaczego powyższe obliczenia dają nam $(1-\epsilon)$ -aproks MWIS ???
odp:
obl MIS

Mamy klastry, to jak obliczyć $(1-\epsilon)$ -aproks MM ?¶

obl MM

Mamy klastry, to jak obliczyć $(1+\epsilon)$ -aproks MDS ?¶

To jest najtrudniejszy z tych problemów...
Wydaje się że nie powinno być żadnego problemu:

obl klastry,
w klastrach obl MDS (nie ma konfliktów na konektorach jak w MIS!),
rozsyłamy rozw po klastrze,
Dlaczego takie podejście nie dziala ???

Próba rozwiązania problemu jak w MM - nieskuteczna...
Problem stanowią wierz wysokiego stopnia, jak się ich pozbyć ?
zapewne znowu „preprocesing” (tak jak było w przypadku MM);
jaki preprocessing ? np. taki:
włączyć do rozw wszystkie wierz wysokiego stopnia i usunąć zdominowane wierz,
pozostanie graf BEZ wierz wysokiego stopnia...
TO NIE DZIAŁA !!!
problem z MDS 2

Zatem jak rozwiązać problem dla MDS ??? MDS rozw 1
... i odpowiedź na powyższe pytanie:
MDS rozw 2

Uwaga: jeśli wagi kraw =1, to nie tylko liczba konektorów jest mała,
ale także liczba wierz brzegowych (końców konektorów) jest mała, w grafie planarnym...

Jak obliczamy klastry w grafie planarnym ?¶

Tu jest opisana procedura obliczająca klastry w czasie $O(\log{n} \log^*n)$
klastry 1
klastry 2
klastry 3

Uwaga: isnieje szybsza procedura obl klastów w czasie $O(\log^*n)$

Jaka jest wada metody klastrów ?
odp: długie komunikaty, np. przy ściaganiu obrazu grafu do centrum...

...

Zadania¶

ZADANIE 60 ciężkie gwiazdy w drzewie ukorzenionym
Dane jest drzewo ukorzenione $T$ , z wagami na krawędziach.
Zaimplementuj algorytm synch znajdujący rozłączne gwiazdy o ŁĄCZNEJ wadze $>\frac12*w(T)$ .
Czas działania algorytmu powinien być rzędu $O({\rm wysokość}(T))$ .
Uwaga: nie należy używać długich komunikatów, tj nie zbierać obrazu całego drzewa w korzeniu!
Zakładamy, że wierz znają wysokość(T).

ZADANIE 61 orientacja kraw z outdeg<=2 w drzewie
Zaimplementuj algorytm znajdujący orientację krawędzi z outdeg<=2 w drzewie nieukorzenionym!

ZADANIE 62 (2pkt) szybka orientacja kraw z outdeg<=2 w drzewie
Jak poprzednie, ale czas działania ograniczony przez $O(\log{n} \log^*n)$ lub lepszy.

ZADANIE 63 ściąganie info o grafie do każdego wierz
Napis algorytm dla grafu kratowego, $k$ x $k$ wierz,
w którym każdy wierz poznaje zbiór ID (id_los) wszystkich wierz; staraj się unikać zbyt długich komunikatów!!

ZADANIE 64 (4pkt) (prj+ref) szybkie ciężkie gwiazdy w drzewie
Obliczać szybko "ciężkie gwiazdy" w drzewie.
Czas działania ograniczony przez $O(\log{n} \log^*n)$ .