# Graph Algorithms

In the winter semester 2020/2021, I teach the course on Graph Algorithms. The lecture covers advanced algorithms for shortest paths, network flows, minimum spanning trees, and some other graph problems. Several graph data structures will be mentioned, too.

The lectures will be held online on Wednesdays from 9:00. You should have received a Zoom link by e-mail.

If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.

date | topics | recording |
---|---|---|

7. 10. | Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings. | video board |

14. 10. | Network flows: Dinitz algorithm and its behavior on special networks. | video board |

21. 10. | Network flows: Scaling algorithm for integer capacities. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm. | video board |

28. 10. |
No lecture today, choose your own holiday :)
| |

4. 11. | Karger-Stein algorithm continued. Shortest paths: general properties, woes with negative cycles, shortest path trees. Relaxation scheme and a proof of its correctness. | video board |

11. 11. | Shortest paths: Bellman-Ford-Moore algorithm as a special case of relaxation. Dijkstra's algorithm and related data structures: various kinds of heaps, array of buckets. | video board |

18. 11. | Data structures for Dijkstra: trees over buckets, multi-level buckets, a sketch of HOT-queues. Shortest paths: Dinic's trick for real edge lengths. Potential reduction and elimination of negative lengths. | video board |

25. 11. | Heuristics for point-to-point shortest paths, the A* algorithm. All-pairs shortest paths and transitive closure: Floyd-Warshall algorithm and its generalization to construction of walk expressions. An algebraic point of view. | video board |

2. 12. | All-pairs shortest paths: making use of matrix multiplication. Divide & conquer algorithm for transitive closure. Seidel's algorithm for undirected unweighted graphs. Introduction to minimum spanning trees: light and heavy edges. | video board |

9. 12. | Minimum spanning trees: Cut lemma, uniqueness, characterization using light edges. Red-blue algorithm and its usual special cases: Jarník's, Borůvka's and Kruskal's algorithm. Union-Find problem. | video board |

16. 12. |
Minimum spanning trees:
Borůvka's algorithm with contractions and filtering.
Minimum spanning trees in planar graphs and minor-closed graph classes.
Density of minor-closed classes and the theorems of Mader and Kostochka+Thomason (without proofs).
Jarník's/Dijkstra's algorithm with Fibonacci heap,
Fredman-Tarjan algorithm (iterated Jarník's algorithm).
[The recording contains only the Fredman-Tarjan algorithm, sorry about that.
You can find the rest in chapters 3.1 and 3.2 of my thesis.]
| video board |

6. 1. |
Representation of trees using ET-sequences and ET-trees.
Fully dynamic connectivity in undirected graphs (Holm, de Lichtenberg, Thorup).
[Not present in the lecture notes, please see chapters 5.2 and 5.3 of my thesis.]
| video board |

## Exams

Exam dates are listed in SIS, please sign up there. I prefer examining in person, but it is hard for you to get to Prague, there are also distance exams listed. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.

You are expected to know the theory presented at the lecture (algorithms, theorems, and proofs) and to be able to apply it to related problems.

## Recommended reading

- In English:
- Alexander Schrijver: Combinatorial Optimization
- The Saga of Minimum Spanning Trees (my Ph.D. thesis, contains detailed discussion of minimum spanning trees and models of computation)
- Last year's lecture

- In Czech:
- Skriptíčka Krajinou grafových algoritmů (mají i v knihovně na MS, ale v elektronické verzi jsou kapitoly navíc a opravené chyby)
- Průvodce labyrintem algoritmů
- Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)