Timeline for Efficient recalculation of the maximum flow when edge capacities are reduced
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2015 at 22:08 | vote | accept | iheap | ||
| Feb 27, 2015 at 22:08 | comment | added | iheap | Great answer! Your example definitely clears up the worst case. However, I am still curious about methods that would perform well on average, or in practice. | |
| Feb 27, 2015 at 21:34 | history | edited | D.W. | CC BY-SA 3.0 |
Elaborate a bit on the construction, and make clearer what is the source vertex and sink vertex.
|
| Feb 27, 2015 at 21:31 | comment | added | D.W. | So $u$ is the source vertex of the new flow network (of $G'$) and $t$ is the sink vertex of the new flow network? OK, that makes sense now. | |
| Feb 27, 2015 at 13:10 | comment | added | R B |
@D.W. - For any network $G,c,s,t$, consider the network $G',c',u,t$, where two vertices are added $u,v$ and the edges $u\to v, v\to s, v\to t$ are added as well, with capacity equal (or larger than) the max flow in $G,c,s,t$. Given a max flow for the new network $u\to v\to t$ with value $f^*$, if I reduce the capacity of $(v,t)$ to 0, this means you need to compute the flow in the reduced network (which is now equivalent to the original network) from scratch. It shows that if $O(VE)$ time is needed for computing flow in a graph, you'll need $O(VE)$ time to compute "reduced edge flow".
|
|
| Feb 27, 2015 at 7:08 | comment | added | D.W. | If $s$ is the source vertex, what does it mean to add the edge $(v,s)$? What are the source and sink vertices in $G'$? I feel like I must be missing some detail here. | |
| Feb 26, 2015 at 10:51 | history | edited | R B | CC BY-SA 3.0 |
added 18 characters in body
|
| Feb 25, 2015 at 19:03 | history | answered | R B | CC BY-SA 3.0 |