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

See also the previous run of this lecture.

This page is maintained by Martin Mareš