FI:MA015 Graph Algorithms - Course Information
MA015 Graph Algorithms
Faculty of InformaticsAutumn 2024
- Extent and Intensity
- 2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
In-person direct teaching - Teacher(s)
- doc. Mgr. Jan Obdržálek, PhD. (lecturer)
- Guaranteed by
- doc. Mgr. Jan Obdržálek, PhD.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics - Timetable
- Mon 16. 9. to Mon 9. 12. Mon 16:00–17:50 A319
- Timetable of Seminar Groups:
- Prerequisites
- IB002 Algorithms I ||(TYP_STUDIA(N)&&FAKULTA(FI))
Knowledge of basic datastructures (e.g priority queues, heaps, graph representations), graph algorithms (e.g. DFS, BFS) and their correctness. Basic complexity theory (e.g. O-notation, classes P/NP/PSPACE, hardness and completeness). - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Informatics (programme FI, B-INF) (2)
- Course objectives
- The course surveys important graph algorithms beyond those typically covered in basic algorithms and data structures courses. Chosen algorithms span most of the important application areas of graphs algorithms.
- Learning outcomes
- At the end of the course students will:
- know and understand efficient algorithms for various graph problems, including: minimum spanning trees, network flows, (globally) minimum cuts, matchings (including the assignment problem);
- be able to prove correctness and complexity of these algorithms;
- be able to use dynamic programming to solve problems on tree-like graphs;
- learn a range of techniques useful for designing efficient algorithms and deriving their complexity. - Syllabus
- Minimum Spanning Trees. Quick overview of basic algorithms (Kruskal, Jarník [Prim], Borůvka) and their modifications. Advanced algorithms: Fredman-Tarjan, Gabow et al. Randomized algorithms: Karger-Klein-Tarjan. Arborescenses of directed graphs, Edmond's branching algorithm.
- Flows in Networks. Revision - Ford-Fulkerson. Edmonds-Karp, Dinic's algorithm (and its variants), MPM (three Indians) algorithm. Modifications for restricted networks.
- Minimum Cuts in Undirected Graphs. All pairs flows/cuts: Gomory-Hu trees. Global minimum cut: node identification algorithm (Nagamochi-Ibaraki), random algorithms (Karger, Karger-Stein)
- Matchings in General Graphs. Basic algorithm using augmenting paths. Perfect matchings: Edmond's blossom algorithm. Maximum matchings. Min-cost perfect matching: Hungarian algorithm.
- Dynamic Algorithms for Hard Problems. Dynamic programming on trees and circular-arc graphs. Tree-width; dynamic programming on tree-decompositions.
- Graph Isomorphism. Colour refinement. Individualisation-refinement algorithms. Tractable classes of graphs.
- Literature
- Teaching methods
- Lecture 2 hrs/week plus 2 hrs tutorial every other week.
- Assessment methods
- Combined written and oral exam.
- Language of instruction
- English
- Further Comments
- Study Materials
The course is taught annually.
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2024/MA015