Therese C. Biedl, Brona Brejova, and Tomas Vinar. Simplifying Flow Networks. In Mogens Nielsen, Branislav Rovan, ed., Mathematical Foundations of Computer Science 2000 (MFCS), 1893 volume of Lecture Notes in Computer Science, pp. 192-201, Bratislava, August 2000. Springer.
Download preprint: 00flow.pdf, 163Kb
Download from publisher: http://springerlink.metapress.com/link.asp?id=wkc4w253x0wfr6ax
Related www page: not available
Bibliography entry: BibTeX
See also: early version
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.
Last update: 10/01/2006