boostorg / boostorg/graph

Karp's minimum mean cycle algorithm

未关闭
#272 6 条评论 0 个 reaction 已指派 1 人 已被 @Becheler 认领 在 GitHub 查看
algorithm
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
20

描述

Dear all,

Are there plans to implement [Karp's minimum mean cycle ](https://www.sciencedirect.com/science/article/pii/0012365X78900110) algorithm in Boost? If not, I would be willing to contribute (although my C++ is quite rusty).

An example implementation is available [here](https://www.geeksforgeeks.org/karps-minimum-mean-average-weight-cycle-algorithm/). 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](https://www.sciencedirect.com/science/article/pii/S0020019017301084?casa_token=NO-MxsCiH54AAAAA:cGZkyJwDDRJllboC2Wm7mDz2JX1xjJFw5Us9Ef_u9SXIEcY99Zx9DDNc2zCGK2cuaUMhR3PQxA).

Thank you,

Gabriel.

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。