Sylabus
Rozklad množiny na třídy ekvivalence, zvětšování tříd (inkrementální udržování komponent souvislosti grafu při přidávání hran).
Tentýž problém s možností backtrackingu nebo obecného odebírání hran.
Splay stromy.
Reprezentace topologie lesa pomocí 'stromů cest'.
Využití 'stromů cest' při hledání blokujícího toku ve vrstevnaté síti v čase $O(m\log m)$.
Využití 'stromů cest' pro inkrementální udržování bloků a bridgebloků.
Problém backtrackingu při údržbě bloků a bridgebloků.
'Cluster'izace - metoda údržby bloků a bridgebloků při obecné operaci delete (nejhorší případ).
'Sparsifikace' (Rozřeďování) - metoda urychlování datových struktur. (dvě obecné varianty, varianta pro rovinné grafy).
SPQR reprezentace (rovinných) grafů.
Top trees - hranově orientovaná clusterizace. Reprezentace topologických lesů s jednoduchým uživatelským rozhraním.
Aplikace Top trees pro udržování bridgebloků a bloků v amortizovaném polylogaritmickém čase a další aplikace Top trees jsou ponechány na Seminář o dynamických datových strukturách (TIN032)
Anotace
Amortizovaná složitost, dynamické datové struktury. Datové struktury charakterizující graf umožňující rychlé odpovědi na základní grafové otázky (souvislost, rovinnost), které je možno rychle modifikovat při postupných změnách grafu.