Grafové algoritmy II
V letním semestru 2025/2026 učím Grafové algoritmy II [NDMI088]. Navazují na Grafové algoritmy ze zimního semestru. Podíváme se na některá pokročilejší témata, jako je například kreslení grafů do roviny, algoritmy pro celočíselně ohodnocené grafy, grafové datové struktury a Pettieho optimální algoritmus na minimální kostry.
Přednášky se odehrávají ve středy od 15:40 v S8.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
Syllabus
| datum | témata [zdroje] | záznam |
|---|---|---|
| 18. 2. | Testování rovinnosti a kreslení do roviny (algoritmus Boyer-Myrvoldová). Předehra: bloková struktura grafů. Kreslení grafů v reverzním DFS pořadí. Detaily potřebné pro lineární čas: externalita, reprezentace bloků. [G11] [BM] | |
| 25. 2. | Pokračování rovinného kreslení (slidy): označení živého podgrafu, procházecí pravidla, sestavení celého algoritmu, důkaz správnosti [G11] [BM]. | video |
| 4. 3. | Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus [S3.3]. | |
| 11. 3. | Plan: Analýza Komlósova algoritmu [S3.3]. Kargerův-Kleinův-Tarjanův algoritmus: randomizovaný algoritmus, který najde minimální kostru v průměrně lineárním čase [S3.5]. | |
| 18. 3. | Přednáška odpadá. |
Materiály
Předchozí běhy přednášky:
Literatura:
- [B] A. L. Buchsbaum et al.: Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998.
- [BM] J. M. Boyer, W. J. Myrvold: On the cutting edge: simplified O(n) planarity by edge addition. In: J. Graph Algorithms and Applications, 2004.
- [G] Skriptíčka Krajinou grafových algoritmů
- [H] H. Kaplan, U. Zwick: A simpler implementation and analysis of Chazelle's soft heaps. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
- [S] The Saga of Minimum Spanning Trees (má dizertační práce o minimálních kostrách a výpočetních modelech)
- [T] Robert E. Tarjan: Applications of Path Compression on Balanced Trees