Therese C. Biedl, Brona Brejova, and Tomas Vinar.
Simplifying flow networks.
In M. Nielsen, B. Rovan, ed.,
Mathematical Foundations of Computer Science 2000 (MFCS),
1893 volume of Lecture Notes in Computer Science,
pp. 192-201, Bratislava, August 2000. Springer.
Preprint, 163Kb | Download from publisher | Early version | BibTeX | MathSciNet
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.