The complexity of Dinitz's algorithm (used to find maximum flow in a network) is O(V²E). I am trying to find a network, which is forcing the algorithm to use as much steps as possible.

I was thinking about a complete graph with some smart configuration of capacities, but I am not able find anything, that would seem to be clearly the worst case.

It is a homework for my Algorithms class, please post advices to point me in the right direction, not complete solutions. Thanks a lot!

(Sorry about my English.)


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.