[comp.theory] Incremental Network Flow Algorithm

rkarri@freya.ucsd.edu (Ramesh Karri) (04/05/91)

Hello,
Can some one post references to an Incremental Algorithm
for Network Flow.

The Problem is : I have a DAG with unit weights on its edges.
(a) I apply the Network flow algorithm (Dinic, Karzanov or some
such algo).

(b) I partition the DAG into two smaller DAGs. I want to find
the minimum cut of the two smaller DAGs. I do not
want to apply the network flow algo all over. I want to use 
info from the previous application of the netflo to get the new
cut values.

Thanks, 
-ramesh 
(rkarri@cs.ucsd.edu)