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 at 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 consultation/lecture. |
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.
- [E] Erik Demaine: Advanced Data Structures (lecture notes)
- [FW] Michael L. Fredman, Dan E. Willard: Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths. In: Journal of Computer and System Sciences 48, pp. 533–551, 1994.
- [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)
- [PD] M. Patrascu, E. Demaine: Lower Bounds for Dynamic Connectivity
See also the previous run of this lecture.