Routing Flow Through a Strongly Connected Graph

It is shown that, for every strongly connected network in which every edge has capacity at least Δ , linear time suffices to send flow from source vertices, each with a given supply, to sink vertices, each with a given demand, provided that the total supply equals the total demand and is bounded by Δ . This problem arises in a maximum‐flow algorithm of Goldberg and Rao, the binary blocking flow algorithm.