Packing and covering paths (Fundamental algorithms, Spring 2023, Lecture 16)
Kent Quanrud · 76:08
This lecture shows that the maximum number of edge-disjoint \(s\)–\(t\) paths equals the size of a minimum \(s\)–\(t\) cut (Menger’s theorem / the unit-capacity max-flow min-cut theorem), and that a natural greedy pat...