Graph Algorithms

In the winter semester 2025/2026, 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 course is scheduled on Wednesdays from 9:00 in room S8 and taught in English this year.

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

date topics
1. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Finding bipartite matchings using flows.
8. 10. Network flows: Symmetric formulation (effective flow). Dinitz algorithm and its behavior on special networks.
15. 10. A virtual lecture: watch the video. Network flows: Scaling algorithm for integer capacities. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: random contractions and their analysis.

Recommended reading

This page is maintained by Martin Mareš