Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in $G$ now new node added/deleted with related edges, I don't like to recalculate maximum flow for new graph, in fact, I want use previous available results for this graph.

Any preprocessing which isn't very time/memory consumer is appropriated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maxflow calculation, now for adding vertex $v$, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to $v$ then goes to destination, but problem is this path should be simple, I couldn't find better than $O(n*E)$ for this case. (Also note that if it was just one path this could be done in $O(n+E)$ but it's not so.)

Also for removing node above idea doesn't work.

share|cite|improve this question
If you don't find anything here, or using a web-search, might be helpful. – Aryabhata Jan 26 '12 at 20:57
@Aryabhata, thanks I'm aware of that, In fact this is a problem in my work (not science at first) but currently seems this is scientific question. – Saeed Jan 26 '12 at 21:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.