Subjects

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

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:	http://mj.ucw.cz/vyuka/ga/

Guarantor:	Mgr. Martin Mareš, Ph.D.
Teacher(s):	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 http://mj.ucw.cz/vyuka/ga/.

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)