Graph Algorithms
The lectures on Graph Algorithms are held on Mondays at 17:20 in S11. In this semester, the course is in English.
| date | topic |
|---|---|
| 15. 10. | Network flows: definitions, basic theorems, Ford-Fulkerson's algorithm. Reduction of bipartite matchings to flows. Definitions of cuts and separators. |
| 22. 10. | Reduction of disjoint path problems to flows and the family of Menger's theorems. Dinitz's algorithm and bounds on its time complexity for various special types of networks. |
| 29. 10. | Perfect matching in regular bipartite graphs via degree splitting. Global vertex and edge connectivity via flows. Nagamochi-Ibaraki algorithm for global weighted edge connectivity: definitions and the main lemma. |
| 5. 11. | Rest of Nagamochi-Ibaraki algorithm, implementation for both weighted and unweighted case. Maximum flow by capacity scaling. Minimum spanning trees: basic structural theorems. |
| 12. 11. | Minimum spanning trees continued: The Red-Blue meta-algorithm and the classical MST algorithms as its special cases. Borůvka's algorithm with contractions applied to planar graphs and more generally minor-closed graph classes. |
| 19. 11. | Binomial heaps and Fibonacci heaps. |
| 26. 11. | Applications of Fibonacci heaps (Dijkstra, MST). Models of computation: Pointer Machine and various flavors of RAM. |
| 3. 12. | Data structures on RAM: Van Emde-Boas Trees. Using RAM as a vector computer: tricks with binary encodings. |
| 10. 12. | Data structures on RAM: bit-parallel B-trees, Q-heaps. MST for integer weights in linear time. |
| 17. 12. | Suffix trees and reduction of string problems to graph problems. Equivalence of suffix trees with suffix arrays. Cartesian trees. |
| 7. 1. | Construction of suffix arrays. The LCA (lowest common ancestor) and RMQ (range minimum query) problems. |
Exams
Regular exams will be held on every Thursday in the exam period (see SIS), feel free to ask me for another date or for consultation.
The exam will cover most of the theory from the lecture (a notable exception being the technical details of Q-heaps) and you can be also given a simple problem to solve.
Literature
My booklet Krajinou grafových algoritmů (in Czech) covers most of the lecture and it contains references to the primary sources (papers, books). It is available in the computer science library or from me.
In English:
- Erik Demaine: Advanced Data Structures (lecture notes)
- Alexander Schrijver: Combinatorial Optimization
In Czech:
- Jiří Demel: Grafy a jejich aplikace (basic algorithms, Kleene algebras)
- Luděk Kučera: Kombinatorické algoritmy (basic algorithms, a little bit outdated)