FI:MA015 Graph Algorithms - Course Information
MA015 Graph AlgorithmsFaculty of Informatics
- 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).
Taught in person.
- 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
- Wed 16:00–17:50 A218
- Timetable of Seminar Groups:
- IB002 Algorithms I ||( TYP_STUDIA ( N )&& FAKULTA ( FI ))
Knowledge of basic graph algorithms and datastructures. Specifically, students should already understand the following datastructures and algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson. Minimum spanning trees: at least one of Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra. Datastructures: priority queues, heaps (incl. Fibonacci), disjoint set (union-find).
- 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
- there are 26 fields of study the course is directly associated with, display
- 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.
- 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.
- Teaching methods
- Lecture 2 hrs/week plus tutorial every other week.
- Assessment methods
- Written exam. To obtain A or B students also have to pass the second, oral part of the exam.
- Language of instruction
- Further Comments
- Study Materials
The course is taught annually.
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2023/MA015