Dynamic Graph Data Structures - NTIN023

• Title: Dynamické grafové datové struktury
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2015
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: Mgr. Vladan Majerech, Dr.
• Class: Informatika Mgr. - Matematická lingvistika
• Classification: Informatics > Theoretical Computer Science
• Pre-requisite : NTIN062
• Is pre-requisite for: NTIN032

Annotation

English

Last update: T_KTI (10.04.2001)

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

Czech

Last update: ()

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.

Aim of the course

Last update: T_KTI (23.05.2008)

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

Course completion requirements

Last update: Mgr. Vladan Majerech, Dr. (06.10.2017)

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.

Literature

Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

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

Syllabus

English

Last update: T_KTI (24.05.2004)

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.

Czech

Last update: T_KTI (24.05.2004)

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)