Benutzer: Gast  Login
Wenn Sie Schwierigkeiten haben, das Dokument zu öffnen, versuchen Sie auch bitte diesen Link
Titel:

Routing flow through a strongly connected graph

Dokumenttyp:
Technical Report
Autor(en):
Thomas Erlebach; Torben Hagerup
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.
Stichworte:
analysis of algorithms; feasible-flow problem; maximum-flow problem; strongly connected graph; depth-first search
Jahr:
1999
Jahr / Monat:
1999-10-01 00:00:00
Seiten/Umfang:
11
 BibTeX