MAX-BALANCING WEIGHTED DIRECTED-GRAPHS AND MATRIX SCALING

A weighted directed graph G is a triple (V, A, g) where (V, A) is a (V,A) is 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. We say 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. We show that there exists a (up to an additive constant) unique potential p(v) for v is-an-element-of V such that (V, A, g(p) is max-balanced where g(a)p = p(u) + g(a) - p(u) + for a = (u,v) is-an-element-of A. We describe an O(\V\2\)A\) algorithm for computing p using an algorithm for computing the maximum cycle-mean of G. Finally, we apply our principal result to the similarity scaling of nonnegative matrices.