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.



Mailing address:
Bronislava Brejova
Katedra informatiky
Mlynska Dolina
842 48 Bratislava

Office: M163

Phone: +421-2-60295217

E-mail: my_surname at