Graph Algorithms - NDMI010
Title: Grafové algoritmy
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
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: English, Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
This course covers advanced graph algorithms and techniques of their design.
Last update: Mareš Martin, Mgr., Ph.D. (28.04.2013)
Course completion requirements -

Oral examination, possibly in distance form.

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

Robert E. Tarjan: Data Structures and Network Algorithms, Philadelphia, 1983

Luděk Kučera: Kombinatorické algoritmy, SNTL, 1989

Alexander Schrijver: Combinatorial Optimization, Springer, 2003

Martin Mareš: Krajinou grafových algoritmů, ITI, Praha, 2007. Dostupné online na

Last update: Mareš Martin, Mgr., Ph.D. (24.04.2012)
Requirements to the exam -

It is necessary to understand the theory presented at the lecture and to be able to apply it.

Last update: Mareš Martin, Mgr., Ph.D. (11.10.2017)
Syllabus -

Network flows: Dinic's algorithm, Malhotra-Kumar-Maheshwari blocking flows, methods for sparse networks and networks with integer capacities.

Testing of k-connectivity: searching for cuts and separators using flows, Karger-Stein's randomized algorithm.

Shortest paths: General relaxation scheme, Dijkstra's algorithm and related data structures (heaps, single- and multi-level buckets). Potential reduction and heuristics based on it. Algebraic connections with matrix multiplications, Kleene algebras. Transitive closures and Seidel's algorithm.

Minimum spanning trees: Fredman-Tarjan's algorithm for general graphs, Fredman-Willard's for integer weights and special algorithms for planar graphs and minor-closed graph classes.

Tree decomposition techniques: clusterization and micro/macro-tree decomposition, the tree ancestor problem and Union-Find problem.

Reduction of string problems to graph problems: suffix trees and their construction in linear time.

Testing of planarity and construction of plannar embeddings.

Last update: Mareš Martin, Mgr., Ph.D. (28.04.2013)