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.
Lectures will be on Wednesdays at 15:40 in room S8.
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