SubjectsSubjects(version: 850)
Course, academic year 2019/2020
  
Dynamic Graph Data Structures - NTIN023
Title in English: 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 [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
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 -
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.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)

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

Course completion requirements - Czech
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 - Czech
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 -
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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html