SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
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.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: Mgr. Martin Mareš, Ph.D. (28.04.2013)
This course covers advanced graph algorithms and techniques of their design.
Course completion requirements -
Last update: Mgr. Martin Mareš, Ph.D. (24.09.2020)

Oral examination, possibly in distance form.

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

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

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

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

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

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html