Karp's minimum mean cycle algorithm #272
Description
Dear all,
Are there plans to implement Karp's minimum mean cycle algorithm in Boost? If not, I would be willing to contribute (although my C++ is quite rusty).
An example implementation is available here. I would include recovering a minimizing cycle in the function; the added cost is small, because the main algorithm runs in O(mn) time (m edges and n vertices), while recovering the minimizer is O(n). For reference, Karp's original paper has a mistake in what concerns recovering the cycle, which was corrected by Chatuverdi and McConnel.
Thank you,
Gabriel.