Graph Algorithms II
I teach Graph Algorithms II [NDMI088] in the summer semester of 2019/2020. 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 lecture is held on Thursdays from 10:40 in room S5.
As the school is currently closed, the class is taught remotely. All course material will be posted on this page with an occasional e-mail announcement.
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] |
|---|---|
| 5. 3. | 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. [G11] [BM] |
| 12. 3. | Reading: Planarity testing continued (slides): walking rules, putting pieces together, proof of correctness [G11] [BM]. |
| 19. 3. | Reading: Verifying minimality of spanning trees: depth reduction using Borůvka trees, the Komlós's algorithm [S3.3]. |
| 26. 3. | Reading: Karger-Klein-Tarjan algorithm: a randomized algorithm which finds the minimum spanning tree in expected linear time [S3.5]. Review of models of computation: Random Access Machine, Pointer Machine, and their many flavors [S2.1]. |
| 3. 4. |
Zoom lecture (blackboard notes,
partial
recording):
Bucket sorting on the pointer machine – graph flattening, tree isomorphism,
string unification [S2.2].
Reading: Topological computations and canonical codes of graphs [S2.2]. |
| 9. 4. | Reading: The Zoo of Ackermann functions and their inverses [S A.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]. |
| 17. 4. | Zoom lecture (blackboard notes, recording): Review of offline LCA and MST verification on the Pointer Machine. |
| 24. 4. |
Zoom lecture (blackboard notes, recording):
A sketch of soft heaps.
Reading: Soft heaps [H], an application to selection [S4.1]. |
| 1. 5. |
Zoom lecture (blackboard notes, recording):
A sketch of the machinery of robust contraction and partitioning to clusters.
Reading: Robust contraction and the partitioning algorithm [S4.2], decision trees [S4.3]. |
| 22. 5. |
Zoom lecture (blackboard notes, recording):
A sketch of Pettie's optimal MST algorithm.
Reading: Optimal MST algorithm [S4.4] |
Exams
There are no exam dates announced. When you want to be examined, just send me and e-mail a couple of days in advance.
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.