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
Form of teaching:	lecture
Guaranteed by:	Department of Applied Mathematics (32-KAM)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2025 to 2025
Duration in semesters:	1
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Maximum number of enrolled students:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Additional information:	http://mj.ucw.cz/vyuka/ga2
Repeated enrollment:	2 / 2 / 2 / 2

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

Opinion survey results SS 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 -

Planarity testing and planar embedding.
Models of computation in graph algorithms: RAM vs. Pointer Machine, vector operations on the RAM, graph decomposition on the PM.
Verifying minimality of spanning trees, Komlós algorithm.
Karger-Klein-Tarjan randomized minimum spanning tree algorithm.
Soft heaps
Pettie's optimal minimum spanning tree algorithm.

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