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.

Amortized, randomized complexity. Dynamic structures representing graph, allowing fast queries for given basic graph properties (connectivity, planarity) and fast updates of underlaying graph.

Naučit základy dynamických datových struktur, zaměřených na grafy.

Zkouška sestává z ústní části (při níž používáme tužku a papír).

Požadavky odpovídají sylabu přednášky v rozsahu prezentovaném na přednášce.

Majerech V.: Datové struktury. (Skripta v elektronické podobě, zatím obsahují pouze některé kapitoly, aktuální verzi je možno získat pomocí: anonymous ftp na @kti.ms.mff.cuni.cz v adresáři /usr/maj)

Westbrook J.: Disertační práce

Tarjan R.E.: Data structures and network algorithms. SIAM, 1983

Články

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)

Disjoint Find Union (unions of equivalence classes starting from singletons) application on incremental connectivity (allowing edge insertions).

The same problem with backtracking.

Splay trees.

How to maintain topology of the forest using 'trees of paths'.

Application of 'trees of paths' - finding blocking flow in layered net in $O(m\log m)$ time.

Application of 'trees of paths' - maintaining bridge blocks or blocks.

Backtracking and maintainance of bridge blocks or blocks.

Clusterisation - maintainance of bridge blocks or blocks with arbitrary delete (worst case).

Sparsification - speeding up method for graph algorithms.

SPQR decomposition of plan(e/ar) graphs.

Top trees - edge oriented clusterisation. Tree representation with friendly user interface.

Application of Top trees on maintainance of bridge blocks and blocks in amortized polylog time, and other Top trees applications are left on TIN032.