Multi-Terminal 0–1 Flow
Yossi Shiloach · SIAM Journal on Computing · 1979
Given an undirected 0–1 flow network with n vertices and m edges, we present an $O(n^2 (m + n))$ algorithm which generates all $\begin{pmatrix} n \\ 2 \end{pmatrix}$ maximal flows between all the pairs of vertices. Since $O(n^2 (m + n))$ is also the size of the output, this algorithm is optimal up to a constant factor.