Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Graph Algorithms 2 - NDMI088

Title:	Grafové algoritmy 2
Guaranteed by:	Department of Applied Mathematics (32-KAM)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2024
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:	not taught
Language:	Czech, English
Teaching methods:	full-time
Additional information:	http://mj.ucw.cz/vyuka/ga2

Guarantor:	Mgr. Martin Mareš, Ph.D.
Class:	Informatika Mgr. - volitelný
Classification:	Informatics > Discrete Mathematics

Opinion survey results Examination dates Schedule Noticeboard

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)