MA015 Graph Algorithms

Faculty of Informatics
Autumn 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 23. 9. to Mon 16. 12. Mon 16:00–17:50 A319
  • Timetable of Seminar Groups:
MA015/01: Fri 4. 10. to Fri 13. 12. each even Friday 8:00–9:50 A218, J. Obdržálek
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
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
    recommended literature
  • MAREŠ, Martin. Krajinou grafových algoritmů. Pracovní verze. ITI, 2015. URL info
  • CORMEN, Thomas H., Charles Eric LEISERSON and Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
    not specified
  • KLEINBERG, Jon and Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info
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.
The course is also listed under the following terms Spring 2003, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2024/MA015