CODEWITHSUNDEEP
algorithmgraphmax-flow
Saeed Amiri
Saeed Amiri

Reputation: 22555

Maximum Flow in Dynamic graphs

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. (if it was just one path or paths was disjoint, this can be done in O(n+E), but it's not so).

Also for removing node above idea doesn't work.

Also my question is not related to another question which looks on dynamic edges adding/removing.

Upvotes: 10

Views: 2108

Answers (3)

Saeed Amiri
Saeed Amiri

Reputation: 22555

I asked this question in CSTheory.StackExchange, For Adding node as I discussed with others I found recalculating is faster than other known algorithms, because recalculation runs on semi sparse graph (residual graph) so it's fast enough also for removing node, there was a good answer, dividing node (which wants to be removed) into two sets, v_in and v_out and calculating flow on residual graph from v_in to v_out, and again calculating flow in residual graph from v_in to v_out by adding infinite edge between source and destination. (and finally comparing their difference and updating residual graph). You can see related Q/A and discussions in Incremental Maximum Flow in Dynamic graphs.

Upvotes: 0

Ofek Ron
Ofek Ron

Reputation: 8580

For adding Vertex v,Use the old Flow f and compute the Residual Graph, then get an Augmenting Path by DFS OutDeg(v) times.

For removing a Vertex v - compute all the flow thats leaving v, say the sum of flow leaving v is a, then while (a>0) find a path P from s to t that is going thro v, and reduce f(P) from the flow and from a.

i think that should help... im more sure on the addition then on the remove, so id love to get corrected in comments :)

Upvotes: 1

Keith Randall
Keith Randall

Reputation: 23265

To dynamically add a vertex v and its associated edges E:

1) Add v by itself to the graph. Since it has no edges, it cannot affect the maximum flow.

2) Add the associated edges E to the graph, one at a time, using the algorithm from this question

Do the reverse for deleting a vertex and its associated edges.

Upvotes: 0

Related Questions