SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   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 2022
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Guarantor: Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: prof. Mgr. Milan Hladík, Ph.D. (02.05.2013)
This course covers advanced graph algorithms, techniques of their design, and related data structures. It extends the Graph algorithms course (NDMI010).
Course completion requirements - Czech
Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)

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ů.

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

Alexander Schrijver: Combinatorial Optimization, Springer, 2003

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

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.

Charles University | Information system of Charles University |