Max-balancing weighted directed graphs and matrix scaling

A weighted directed graph G is a triple where is a directed graph and g is an arbitrary real-valued function defined on the arc set A. Let G be a strongly-connected, simple weighted directed graph. It is stated that G is max-balanced if for every nontrivial subset of the vertices W , the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. It is shown that there exists a (up to an additive constant) unique potential for such that is max-balanced where for . The authors describe an algorithm for computing p using an algorithm for computing the maximum cycle-mean of G .Finally, they apply their principal result to the similarity scaling of nonnegative matrices.