# FI:MA015 Graph Algorithms - Course Information

## MA015 Graph Algorithms

**Faculty of Informatics**

Autumn 2023

**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. **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**- Wed 16:00–17:50 A218
- Timetable of Seminar Groups:

*J. Obdržálek* **Prerequisites**-
**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. **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 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**- English
**Further Comments**- Study Materials

The course is taught annually.

- Enrolment Statistics (recent)

- Permalink: https://is.muni.cz/course/fi/autumn2023/MA015