Routing flow through a strongly connected graph

Document type:: Technical Report
Author(s):: Thomas Erlebach; Torben Hagerup
Title:: Routing flow through a strongly connected graph
Abstract:: It is shown that, for every strongly connected network in which every edge has capacity at least D, 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 D. This problem arises in a new maximum-flow algorithm of Goldberg and Rao.
Keywords:: analysis of algorithms; feasible-flow problem; maximum-flow problem; strongly connected graph; depth-first search
Year:: 1999
Year / month:: 1999-10-01 00:00:00
Pages:: 11
BibTeX

Occurrences: