Karp's minimum mean cycle 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 还没有评估数据。