Prerequisities

There are no formal requirements. However you are expected to know basic graph algorithms and datastructures, to the  extent covered by the course IV003 Algorithms and Data Structures II. More specifically, these graph algorithms and datastructures:

• Graph searching: DFS, BFS.
• Network flows: Ford-Fulkerson, Golderg (push-relabel).
• Minimum spanning trees: Kruskal, Jarník (Prim), Borůvka.
• Shortest paths: Bellman-Ford, Dijkstra.
• Datastructures: heaps (incl. Fibonacci), disjoint set (union-find), ...

Exam

There will be only a final written exam, no grading throughout the semester. The questions will be in English, but (on some dates) you are allowed to answer in Czech if you prefer to. 
To get grades A or B, you need to score enough points in the written part, and then take a followup oral part of the exam. (For grades C-F no oral part, only the written exam.)

Exam dates: there will be one chance to take the exam in the last week of the semester, otherwise multiple dates in the exam period, as usual.

You are allowed to complete the course with colloqium (k) or zápočet (z) if you prefer to.

Tutorials

2 hrs every second week of the semester. Attendance is compulsory, but you are allowed to miss one without giving any reason.

Tutors: Jan Obdržálek, Daniel McNulty

Literature

There is no single book which covers the entire course. For each lecture I'll be giving a list of papers/book chapters which cover the topic. The papers will be mostly research or survey paper freely available to students of this course. Some general books:

• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms
• J. Kleinberg, E. Tardös: Algorithm Design
• D. Kozen: Design and Analysis of Algorithms
• R. Tarjan: Data Structures and Network Algorithms

Dates

19. 9. The classical algorithms: Kruskal, Jarník, Borůvka
26. 9. Advanced Algorithms: Fredman-Tarjan, Gabow et al.
3. 10. Randomized algorithm of Karger-Klein-Tarjan; Arborescences, Edmonds' branching algorithm

Reading

J. Eisner: State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion (1997) [PDF]

Marvelous survey of algorithms which appeared before 1997. See chapters 3 (Kruskal, Jarník), 4 (Borůvka and contractions), 5 (Fredman-Tarjan; Gabow et al.) and 7 (Karger-Klein-Tarjan)

H. Gabow, Z. Galil, T. Spencer, R. Tarjan (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica 6 (2): 109. doi:10.1007/bf02579168

Very clear presentation of the algorithm of Gabow et al.

T. Chan: Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees (1998)  doi:10.1016/S0020-0190(98)00129-X

The simple proof of the sampling lemma used in Karger-Klein-Tarjan.

J. Kleinberg, E. Tardos: Algorithm Design [Section 4.9] [PDF]

Read this for the Edmonds' branching algorithm for min-cost arborescences.

Historical references

• R. Graham, P. Hell (1985). "On the history of the minimum spanning tree problem", Annals of the History of Computing 7 (1): 43–57,doi:10.1109/MAHC.1985.10011
• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nešetřilová. 
• M. Fredman, R. Tarjan (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM 34 (3): 596.doi:10.1145/28869.28874.
• H. Gabow, Z. Galil, T. Spencer, R. Tarjan (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica 6 (2): 109. doi:10.1007/bf02579168
• R. Karger, P. Klein, R. Tarjan (1995). "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery 42 (2): 321–328, doi:10.1145/201019.201022
• Chu, Y. J.; Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica 14: 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", J. Res. Nat. Bur. Standards 71B: 233–240, doi:10.6028/jres.071b.032

Slides

Dates

3. 10.  Intro.
10.10. Revision: Ford-Fulkerson. Algorithms of Edmonds-Karp, Dinic and MPM.

Reading

D. Kozen: The Design and Analysis of Algorithms. [Chapters 16-18] [PDF]

Contains Edmonds-Karp, Dinic, MPM (Three Indians)

S. Even, R. E. Tarjan (1975). "Network Flows and Testing Graph Connectivity". SIAM Journal on Computing 4 (4): 507-518. doi:10.1137/0204043 [PDF]

Read this for Dinic's algorithm with unit capacities.

Goldberg, Tarjan: Efficient Maximum Flow Algorithms. Communications of the ACM 57 (8) doi:10.1145/2628036

Very nice recent overview of the current state of the maximum flow algorithms. 

Historical references

• Yefim Dinitz (2006). Dinitz' Algorithm: The Original Version and Even's Version
• Harris, Ross (1955). Fundamentals of a Method for Evaluating Rail Net Capacities
• Ford, Fulkerson (1956). "Maximal flow through a network". Canadian Journal of Mathematics 8: 399. doi:10.4153/CJM-1956-045-5.
• Edmonds, Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems".Journal of the ACM  19 (2): 248–264. doi:10.1145/321694.321699.

Slides

Dates

17. 10. Gomory-Hu trees
24. 10. Node identification algorithm of Stoer and Wagner, randomized algorithms of Karger and Karger-Stein

Reading

The Stoer-Wagner algorithm is best described in the original paper:

• Stoer, M.; Wagner, F. (1997). "A simple min-cut algorithm". Journal of the ACM 44 (4): 585. doi:10.1145/263867.263872.

All three algorithms are described in the following textbook I mostly follow:

• Cook, Cunningham, Pulleybank, Schrijver: Combinatorial optimization [Section 3.5] [PDF]

For more details about the algorithms I also recommend reading these original papers:

• Gomory, R. E.; Hu, T. C. (1961). "Multi-terminal network flows". Journal of the Society for Industrial and Applied Mathematics 9. doi:10.1137/0204043 [PDF]
• Karger, David R.; Stein, Clifford (1996). "A new approach to the minimum cut problem". Journal of the ACM 43 (4): 601. doi:10.1145/234533.234534

Historical references

• H. Nagamochi and T. Ibaraki (1992). "Computing edge-connectivity in multigraphs and capacitated graphs". SIAM J. Disc. Meth., 5:54-66. doi:10.1137/0405004

Slides

Dates

31. 10. Introduction to matchings, algorithm for perfect matchings in bipartite graphs, Edmonds' algorithm for perfect matchings in general graphs
7. 11. Edmonds' algorithm for maximal matchings; the assignment problem; weighted matchings in bipartite graphs (Hungarian algorithm)

Reading

Cook, Cunningham, Pulleybank, Schrijver: Combinatorial optimization [Section 5.1] [PDF]
For the Hungarian algorithm try the interactive materials at TU Munchen [link]

Historical references

• Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4

Slides

Dates

14. 11. dynamic programming on trees and circular-arc graphs; treewidth
21. 11. dynamic programming on tree decompositions; nice tree decompositions

Reading

Kleinberg, Tardos: Algorithm Design [PDF]

Algorithm for Vertex Cover on tree decompositions:
R. Niedermayer: Invitation to Fixed-Parameter Algorihtms: [PDF]
 

Additional material

If you want to know more, or want to look at things from a slightly different, more theoretical angle, Jiri Fiala (MFF UK) has a nice text called Graph minors, decompositions and algorithms

Slides

Dates

28. 11. rooted tree isomorphism (AHU algorithm), tree isomorphism
05. 12. colour refinement

Reading

For rooted tree isomorphism, read the original Aho-Hopcrodt-Ullman book [PDF]
(the algorithm propper starts at page 84, you can skip the previous pages if not interested)

For tree isomorphism:
Douglas M. Campbell and David Radford (1991): "Tree Isomorphism Algorithms: Speed vs. Clarity". Mathematics Magazine, Vol. 64, No. 4 (Oct., 1991), pp. 252-261 [JSTOR]

For colour refinement:
Progress of various Colour Refinement algorithms when executed on the graph $P_6$ [PDF]
slides ;)

Additional material

The Nauty Traces tool.

Slides