SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Graph Algorithms 2 - NDMI088
Title: Grafové algoritmy 2
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: summer
E-Credits: 3
Hours per week, examination: summer 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, English
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Annotation -
This course covers advanced graph algorithms, techniques of their design, and related data structures. It extends the Graph algorithms course (NDMI010).
Last update: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)
Course completion requirements - Czech

Předmět je zakončen zkouškou, u níž se ověřuje porozumění látce z přednášky a schopnost aplikovat ji na řešení obdobných problémů.

Last update: Mareš Martin, Mgr., Ph.D. (02.03.2018)
Literature -

Alexander Schrijver: Combinatorial Optimization, Springer, 2003

Last update: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)
Syllabus -

Network flows: Goldberg's algorithm and its kin.

Accelerating flow algorithms on sparse graphs using Sleator-Tarjan Trees.

Description of minimum cuts by Gomory-Hu Trees.

Data structures for integers: Van Emde-Boas Trees, Q-Heaps, atomic heaps.

Minimum spanning trees: Integer algorithms, verification of minimality, Pettie's optimal algorithm.

Last update: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)
Charles University | Information system of Charles University |