In the winter semester 2018/2019, I teach the course on Graph Algorithms (this year in English). Lectures are scheduled on each Thursday from 12:20 in S8.
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.
If you want to contact me and consult anything, you are welcome to visit me in room S322 or to write me an e-mail to email@example.com.
|11. 10.||Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings, cuts, and separators.|
|18. 10.||Dinitz algorithm and its behavior on special networks. Scaling algorithm for integer capacities.|
|15. 10.||Plan: Mengerian theorems and related algorithmic problems. Globally minimum cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm.|
- In English:
- Alexander Schrijver: Combinatorial Optimization
- The Saga of Minimum Spanning Trees (my PhD thesis, contains detailed discussion of minimum spanning trees and models of computation)
- In Czech: