Graph Algorithms II
I teach Graph Algorithms II [NDMI088] in the summer semester of 2025/2026. It is a follow-up course for Graph Algorithms from the winter semester. We will discuss more advanced topics like algorithms for integer-valued graphs, data structures for graphs, and Pettie's optimal algorithm for minimum spanning trees.
Time and space coordinates will be agreed upon at Úmluva.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
Course material
Previous runs of the lecture:
Literature:
- [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ů [in Czech]
- [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 (my Ph.D. thesis on minimum spanning trees and models of computation)
- [T] Robert E. Tarjan: Applications of Path Compression on Balanced Trees