| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4950863 | Information Processing Letters | 2017 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mmanu Chaturvedi, Ross M. McConnell,