Publication details

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.