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