Publication details

Therese C. Biedl, Brona Brejova, Tomas Vinar. Simplifying Flow Networks. Technical Report CS-2000-07, Dept. of Computer Science, University of Waterloo, March 2000.
Preprint, 370Kb | Download from publisher | BibTeX

Abstract

Maximum flow problems appear in many practical applications.
In this paper, we study how to simplify a given directed flow network
by finding edges that can be removed without changing the value of the
maximum flow.  We give a number of approaches which are increasingly
more complex and more time-consuming, but in exchange they remove more
and more edges from the network.