Předmět Graph Algorithms (MA015)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu MA015 - Graph Algorithms, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
Materiál | Typ | Datum | Počet stažení |
---|
Další informace
Cíl
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.
Osnova
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).
Literatura
doporučená literaturaMAREŠ, Martin. Krajinou grafových algoritmů. Pracovní verze. : ITI, 2015. URL infoCORMEN, Thomas H., Charles E. LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989. xvii, 1028. ISBN 0-07-013143-0. info
Požadavky
MB005 Základy matematiky ||( MB101 Lineární modely && MB102 Dif. a integrální počet )||( MB201 Lineární modely B && MB102 Dif. a integrální počet )||( MB101 Lineární modely && MB202 Dif. a integrální počet B )||( MB201 Lineární modely B && MB202 Dif. a integrální počet B )||( PřF:M1120 Diskrétní matematika )|| 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.
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
Mgr. Jan Obdržálek, PhD.Frédéric Dupont Dupuis, Ph.D.Mgr. Bc. Tomáš Janíkprof. RNDr. Petr Hliněný, Ph.D.