Solution Found!
Suppose someone presents you with a solution to a max-flow problem on some network. Give
Chapter 7, Problem 7.19(choose chapter or problem)
Suppose someone presents you with a solution to a max-flow problem on some network. Give alinear time algorithm to determine whether the solution does indeed give a maximum flow.
Questions & Answers
QUESTION:
Suppose someone presents you with a solution to a max-flow problem on some network. Give alinear time algorithm to determine whether the solution does indeed give a maximum flow.
ANSWER:Step 1 of 2
To check if the given solution indeed gives a max solution:
Firstly, compare the flow of each edge capacity to each edge to verify that the solution is a valid flow or not.
If the solution gives the valid flow, then the compare the residual graph O(|E|) and augmenting path, which using BFS is O(|V|+|E|).
If the augmented path exists, the solution is not a maximum flow.