0
$\begingroup$

The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm will not terminate? Assume integer capacities for each edge.

Edit: I learned that even if the back-flows are ignored, with each iteration of the algorithm, we need to show that the capacity of at least one edge will decrease. If this is the case, then when continuously iterating through and finding paths within the network, we will eventually get to a point where all edges become "filled" in the worst case. When this happens, the algorithm must terminate.

$\endgroup$
  • $\begingroup$ Welcome to CS.StackExchange! What have you tried towards the solving the problem so far? You should include it in the question description. $\endgroup$ – LastIronStar Nov 20 '17 at 6:30
  • $\begingroup$ I updated the question now $\endgroup$ – Dr C Nov 21 '17 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.