Maximum flow algorithms for interactive application

From: Kai-Peter Bäckman (yg-boost-users_at_[hidden])
Date: 2003-06-17 06:23:12

 Hello fellow Boost users,

 I have been using the boost.graph library in an interactive application
for solving the maximum flow problem using the push_relabel algorith.
The application consists of the user building the graph network
interactively, node by node and edge by edge. Currently the maximum flow
for the whole system is recalculated after each change. In addition to
the total maximum flow the individual flows in all edges are used by the
application.

 The problem is that interactivity is lost when the amount of nodes
approaches 10k with the number of edges varying between 20k-40k.

 My question is: Is there an algorithm that would let me quickly
calculate the changed maxium flow solution after each change without
needing to do the global calculations again? The idea here would be to
amortize the running time over each interactive change and thus keep
response times acceptable (<200ms). My intuition tells me something like
this should be possible, but I don't want to reinvent the wheel.

 Thank you in advance. If someone replies by email I will summarize to
the group.

 Have a nice summer.

--
Kai-Peter Bäckman, kai-peter.backman_at_[hidden]
http://www.mistaril.com - Space Station Manager - PC strategy game