Karp's minimum mean cycle algorithm
- Lenguaje dominante
- C++
- Estrellas
- 392
- Forks
- 239
- Merge medio
- 1 d 11 min
- PR fusionados (30 d)
- 20
Descripción
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.
Guía de contribución
Evaluación
Este issue todavía no se ha evaluado.