MA015 Graph Algorithms

Fakulta informatiky
podzim 2023
Rozsah
2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
doc. Mgr. Jan Obdržálek, PhD. (přednášející)
Garance
doc. Mgr. Jan Obdržálek, PhD.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
St 16:00–17:50 A218
  • Rozvrh seminárních/paralelních skupin:
MA015/01: Po 18. 9. až Po 11. 12. každé sudé pondělí 10:00–11:50 A319, J. Obdržálek
Předpoklady
IB002 Algoritmy a datové struktury ||(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).
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
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.
Výstupy z učení
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.
Osnova
  • 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.
Literatura
    doporučená literatura
  • MAREŠ, Martin. Krajinou grafových algoritmů. Pracovní verze. ITI, 2015. URL info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Výukové metody
Lecture 2 hrs/week plus tutorial every other week.
Metody hodnocení
Written exam. To obtain A or B students also have to pass the second, oral part of the exam.
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2003, podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2024.