Graph Algorithms II
I teach Graph Algorithms II [NDMI088] in the summer semester of 2021/2022. 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.
The lectures will be on Tuesdays from 10:40 in room S322. I will teach in Czech or English depending on the audience.
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] |
| 1. 3. | Planarity testing continued (slides): discovering the live subgraph, walking rules, putting pieces together, proof of correctness [G11] [BM]. |
| 8. 3. | Verifying minimality of spanning trees: depth reduction using Borůvka trees, the Komlós's algorithm [S3.3]. |
| 15. 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]. |
| 22. 3. | 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. Bucket sorting on the PM #1: graph flattening [S2.2]. |
| 29. 3. | Linear-time implementation of Komlós's algorithm on the RAM [S3.4]. Bucket sorting on the PM #2: tree isomorphism [S2.2]. |
| 5. 4. | Bucket sorting on the PM #3: string unification, topological computation, and canonical codes of graphs [S2.2]. The Zoo of Ackermann functions and their inverses [S A.3]. |
| 12. 4. | 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]. Introduction to soft heaps [H], an application to selection [S4.1]. |
| 19. 4. | Soft heaps [H]. |
| 26. 4. | Robust contraction and the partitioning algorithm [S4.2]. |
| 3. 5. | Decision trees [S4.3]. Optimal MST algorithm [S4.4]. |
| 10. 5. | No lecture today. |
| 17. 5. | Consultation. |
Exams
There are exam dates listed in SIS. Please sign up there or send me an e-mail if no date suits you.
You are expected to know the material from the lectures, to understand it, and to be able to modify the algorithms to solve similar problems. You are allowed to bring a cheat sheet on a single A4 page.
Recommended reading
- [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)
See also the previous run of this lecture including video recordings.