Skip to content
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.

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

Improve Time Complexity for MCF and Assignment Problem #1087

Open
bqi343 opened this issue May 14, 2023 · 1 comment
Open

Improve Time Complexity for MCF and Assignment Problem #1087

bqi343 opened this issue May 14, 2023 · 1 comment

Comments

@bqi343
Copy link
Contributor

bqi343 commented May 14, 2023

It is mentioned that MCF and the assignment problem can be solved in O(mn + Fm*log n) time and O(n^3) time, respectively, but the provided code uses SPFA, which does not run in these time complexities. Here are some implementations that do run in the desired time complexities:

@adamant-pwn
Copy link
Member

Hi, thanks for pointing that out! There is actually a separate article on the original e-maxx about Hungarian algorithm. I'd be happy to accept a pull request that changes the algorithm, but using your code directly is complicated, as it depends on various macros and is generally not very well structured for algorithm exposition, I'd say :(

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

No branches or pull requests

2 participants