Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!lll-winken!iggy.GW.Vitalink.COM!pacbell.com!ucsd!sdcc6!freya!rkarri
From: rkarri@freya.ucsd.edu (Ramesh Karri)
Newsgroups: comp.theory
Subject: Incremental Network Flow Algorithm
Message-ID: <17995@sdcc6.ucsd.edu>
Date: 5 Apr 91 07:58:31 GMT
Sender: news@sdcc6.ucsd.edu
Organization: CSE Dept., UC San Diego
Lines: 18


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)