Login
- Dokumenttyp:
- Technical Report
- Autor(en):
- Thomas Erlebach; Torben Hagerup
- Titel:
- 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.
- 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