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:

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