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. Topological graph computation, and canonical codes of graphs [S2.2]. The Zoo of Ackermann functions and their inverses [SA.3].
2. 5. 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] [T].
9. 5. Soft heaps [H]: interface, example with finding pivots, construction and analysis of corruption.
16. 5. Soft heaps [H]: cheat sheet, time complexity. Back to MST: Generalized contraction [S4.2].
23. 5. Robust contraction and the partitioning algorithm [S4.2]. Decision trees [S4.3]. Optimal MST algorithm [S4.4].

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, which you made yourself.

I will not ask for proofs of technical lemmas around the optimal MST algorithm.

Course material

Previous runs of the lecture:

Literature:

This page is maintained by Martin Mareš