1
$\begingroup$

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.)

$\endgroup$

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.