Graph Algorithms II
I teach Graph Algorithms II [NDMI088] in the summer semester of 2023/2024. 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 Thursdays at 9:00 in room S11.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
Syllabus
| date | topics [sources] |
|---|---|
| 22. 2. | Planarity testing and planar embedding (Boyer-Myrvold algorithm). Overture: block structure of graphs via DFS. Embedding a graph in reverse DFS order. Details necessary for linear time: externality, representation of blocks. [G11] [BM] |
| 29. 2. | No lecture today. |
| 7. 3. | Planarity testing continued (slides): discovering the live subgraph, walking rules, putting pieces together, proof of correctness [G11] [BM]. |
| 14. 3. | Verifying minimality of spanning trees: depth reduction using Borůvka trees, the Komlós's algorithm [S3.3]. |
| 21. 3. | No lecture today. |
| 28. 3. | Analysis of Komlós's algorithm [S3.3]. Karger-Klein-Tarjan algorithm: a randomized algorithm which finds the minimum spanning tree in expected linear time [S3.5]. |
| 4. 4. | KKT algorithm continued [S3.5]. Review of models of computation: Random Access Machine, Pointer Machine, and their many flavors [S2.1]. Constant-time operations with tiny vectors on the RAM. |
| 11. 4. | Linear-time implementation of Komlós's algorithm on the RAM [S3.4]. |
| 18. 4. | Bucket sorting on the PM: graph flattening, tree isomorphism, string unification. |
| 25. 4. | Plan: Topological graph computation, and canonical codes of graphs [S2.2]. The Zoo of Ackermann functions and their inverses [SA.3]. An offline algorithm for lowest common ancestors on the Pointer Machine [B1–4] (observe that sections 4.1–4.3 of the paper are equivalent to our framework of topological graph computations). Applying the same approach to verification of minimum spanning trees: developing Link-Eval from Union-Find, generating decision trees using Komlós's algorithm [B5]. |
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)