Dates

17.10. (Gomory-Hu trees)

24. 10. (Node identification algorithm of Nagamochi and Ibaraki, randomized algorithms of Karger and Karger-Stein)

Reading

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

The above book section is quite dense. For more details I 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]
• Stoer, M.; Wagner, F. (1997). "A simple min-cut algorithm". Journal of the ACM 44 (4): 585. doi:10.1145/263867.263872.
• 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