These problems have applications to embedded systems[2] and logic chip design.
[citation needed] Lawler presented an algorithm for computing a minimum mean weight cycle using O(log |V|) calls to an algorithm for solving the negative cycle problem.
Let G be any directed graph, and let s be a fixed vertex in G. For every nonnegative integer k and every vertex v in G, define Hk(v) as the maximum cost of a path of length k from s to v; if no such path exists, then Hk(v) = minus infinity.
It is sufficient to prove the lemma for the case in which the maximum mean cycle weight equals 0.
When t is sufficiently large, Pt has a prefix of length n; it is a maximum-cost path from s to some node w'.
Therefore, when the maximum mean cycle cost is 0, (*) equals 0, which is sufficient to complete the proof.
It is possible to compute Hk using dynamic programming in time O(|E||V|); then it is possible to find the maximum mean cycle weight using (*).
[2] Albrecht, Korte, Schietke and Vygen[3] relate the problem of maximum mean weight cycle to the minimum balance problem: find a potential function[disambiguation needed] such that the "slacks" of all edges are optimally balanced.
They show that parametric shortest path can be used for solving more general variants of these problems, with constraints that are relevant to optimizing the clock schedule of a logic chip.