科研之友
微信
新浪微博
Facebook
分享链接
摘要
In a directed graph with edge weights, the mean weight of a directed cycle is the weight of its edges divided by their number. The minimum cycle mean of the graph is the minimum mean weight of a cycle. Karp gave a characterization of minimum cycle mean and an O(nm) algorithm to compute it, where n is the number of vertices and m is the number of edges. However, an algorithm he suggested for identifying a cycle with this mean weight is not correct. We propose an alternative.
- 出版日期2017-11
