Resistance bounds for first-passage percolation and maximum flow

Suppose that each edge e of a network is assigned a random exponential pass age time with mean r(e). Then the expected first-passage time between two v ertices is at least the effective resistance between them for the edge resi stances [r(e)]. Similarly, suppose each edge is assigned a random exponenti al edge capacity with mean c(e). Then the expected maximum flow between two vertices is at least the effective conductance between them fbr the edge c onductances [c(e)]. These inequalities are dual to each other for planar gr aphs and the second is tight up to a factor of 2 for trees; this has implic ations for a herd of gnus crossing a river delta. (C) 1999 Academic Press.