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.