New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Wrong complexity for Dinics #403

Open

BlueskyFR opened this issue Oct 6, 2023 · 0 comments

BlueskyFR commented Oct 6, 2023

https://github.com/williamfiset/Algorithms/blob/da50861a53fc2f6642cfc7d82c285166f41d03e2/src/main/java/com/williamfiset/algorithms/graphtheory/networkflow/Dinics.java#L9C1-L9C1

Hey, I think the actual time complexity for Dinics algorithm is O(E^2V), not O(EV^2) as written.

Is the implementation non-optimal or is the comment simply wrong?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment