Institution: Stanford University, Department of Computer Science

Title: Multi-terminal 0-1 flow

Author: Shiloach, Yossi

Date: April 1978

Abstract: 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 ($n\choose 2$) 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/78/653/CS-TR-78-653.pdf