Timeline for Incremental Maximum Flow in Dynamic graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2015 at 10:11 | comment | added | Chet | Any ideas how you'd do this if you want to change an edge capacity? | |
| Feb 20, 2012 at 13:02 | vote | accept | Saeed | ||
| Feb 18, 2012 at 15:40 | history | edited | Dmytro Korduban | CC BY-SA 3.0 |
for the sake of homogeneity
|
| Feb 13, 2012 at 15:56 | comment | added | Dmytro Korduban | When you push 1 unit of flow from $v$ to $u$, you decrease $c_f(v,u)$ by 1 and increase $c_f(u,v)$ by 1 because the flow is anti-symmetric ($f(v,u) = -f(u,v)$). This defines true residual graph, so everything works well in it. | |
| Feb 13, 2012 at 15:49 | comment | added | Saeed | As I understand in removing node, By $\tilde{f^v}$ you will calculate flow in residual graph, but I think it's not true, in fact in residual graph you have some edges which used in calculating $f^v$ and you should add extra capacity to this edges, then calculating $\tilde{f^v}$, then using $\Delta$. | |
| Feb 13, 2012 at 15:44 | comment | added | Dmytro Korduban | After reading last vzn's answer I've found the similar approach described at the page 90 of this. | |
| Feb 13, 2012 at 14:58 | history | answered | Dmytro Korduban | CC BY-SA 3.0 |