MA015 Graph Algorithms

Faculty of Informatics
Autumn 2015
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
doc. Mgr. Jan Obdržálek, PhD. (lecturer)
Frédéric Dupont Dupuis, Ph.D. (seminar tutor)
Mgr. Bc. Tomáš Janík (seminar tutor)
prof. RNDr. Petr Hliněný, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Mon 12:00–13:50 D2
  • Timetable of Seminar Groups:
MA015/T01: Wed 23. 9. to Tue 22. 12. Wed 13:00–14:35 106, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MA015/01: each odd Monday 10:00–11:50 C525, F. Dupont Dupuis
MA015/02: each even Monday 10:00–11:50 C525, F. Dupont Dupuis
MA015/03: each odd Friday 8:00–9:50 C511, F. Dupont Dupuis
MA015/04: each even Friday 8:00–9:50 C511, F. Dupont Dupuis
MA015/05: each odd Monday 16:00–17:50 A319, J. Obdržálek
MA015/06: each even Monday 16:00–17:50 A319, J. Obdržálek
Prerequisites
MB005 Foundations of mathematics ||( MB101 Linear models && MB102 Calculus )||( MB201 Linear models B && MB102 Calculus )||( MB101 Linear models && MB202 Calculus B )||( MB201 Linear models B && MB202 Calculus B )||( PřF:M1120 Discrete Mathematics )||PROGRAM(N-IN)||PROGRAM(N-AP)
Knowledge of basic graph algorithms, to the extent covered by the course IV003 Algorithms and Data Structures II. Specifically, students should already understand the following algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson, Golderg (push-relabel). Minimum spanning trees: Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra.
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 24 fields of study the course is directly associated with, display
Course objectives
At the end of the course students will under know and understand important graph algorithms beyond the reach of standard algorithms and data structures courses. Covered algorithms span most of the important application areas of graphs algorithms. The students also should be able to choose an algorithm best suited for a given task, modifying it when necessary, and estimate its complexity.
Syllabus
  • Cover problems: vertex cover, dominating set, feedback vertex set, feedback arc set. Parameterized complexity of algorithms.
  • Dynamic algorithms on tree-like structures: algorithms for trees, graphs of bounded tree-width, path-width, clique-width, oriented tree-like graphs.
  • Graph isomorphism: trees, planar graphs, general-case heuristics (colour coding).
  • Planar drawing and testing: path addition method, PQ/SPQR trees, Boyer-Myrwold algorithm.
  • Network flows: Edmonds-Karp algorithm. Dinic's algorithm and its modifications (e.g. unit capacities, integer capacities). Three Indians algorithm. Minimum-cost flow algorithms.
  • Shortest paths: A* algorithm, reach-based algorithms, hub labelling, hierarchical decompositions, distance oracles.
  • Spanning trees: modifications of Borůvka's and Jarnik§s algorithm for particular input instances (e.g. planar graphs). Steiner trees.
  • Cuts (non-flow based algorithms): Gomory-Hu trees, globally minimum cut, Nagamochi-Ibaraki algorithm, randomized algorithms (Karger-Stein).
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
Teaching methods
Lecture 2 hrs/week plus 2hr tutorial each other week.
Assessment methods
Written 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 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2015, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2015/MA015