Report Number: CS-TR-78-653
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.