stuart@rochester.ARPA (11/14/86)
From: Stuart Friedberg <stuart>
Can anyone provide references to algorithms for incremental computation
of network flow? That is, suppose I have a (not necessarily connected)
network with computed flows and add or delete an edge. How can I
compute the flow of the resulting graph quickly from its predecessor?
My application is not a standard graph problem, but can be viewed as a
multicommodity system where all edges have capacity of one for each
commodity and flows do not sum. (Like wires carrying distinct electric
signals) Loops and multiple paths between vertices have to be handled.
Graph algorithms are not a specialty of mine, but I understand what's
in Even's book as a starting point. Unfortunately, the network flow
computations presented in that and similar texts start from scratch and
complexity is presented in terms of the complete computation. I am
much more interested in an on-line algorithm with small incremental
cost for arbitrary edge insertions and deletions; the overall cost is
not important.
If anyone can provide pointers to such incremental flow computations,
I would greatly appreciate it. If anyone can tell me authoritatively
that such algorithms don't exist, I may polish and publish my current
kludge, just to encourage someone to do it well.
Stu Friedberg {seismo, allegra}!rochester!stuart stuart@rochester.arpa
Computer Science Department
University of Rochester
Rochester, New York 14627