1

Let $G=(V,E)$ be a flow network from $s$ to $t$.

I have a maximum flow $f\colon E\to Z$ that was calculated using Ford-Fulkerson.

How can I efficiently update $f$ when I need to subtract the capacity of a specific edge $e^* \in E$ by 1

($c(e^*)=c(e^*)-1$)

Lee
  • 811
  • If the edge does not cross your minimum cut, then at most you have to rerun Ford-Fulkerson on the portion of the graph on the same side of the minimum cut as e. If the edge is along the minimum cut, then I doubt you can do much better than rerunning the entire algorithm. – DanielV Feb 11 '16 at 22:51

0 Answers0