A characterization of the minimum cycle mean in a digraph

A simple characterization of λ∗, as well as an algorithm for computing it efficiently, is given, which is called the minimum cycle mean.

Abstract

Let C = (V,E) be a digraph with n vertices. Let f be a function from E into the real numbers, associating with each edge e ∈ E a weightƒ(e). Given any sequence of edges σ = e1,e2,…,ep define w(σ), the weight of σ, as ∑i = 1p ƒ(ei), and define m(σ), the mean weight of σ, as w(σ)⧸p. Let λ∗ = minCm(C) where C ranges over all directed cycles in G; λ∗ is called the minimum cycle mean. We give a simple characterization of λ∗, as well as an algorithm for computing it efficiently.