 |
|
|||
| Authors: | Thomas Erlebach, Torben Hagerup |
| Group: | Theory of Communication Networks |
| Type: | Article |
| Title: | Routing flow through a strongly connected graph |
| Year: | 2002 |
| Pub-Key: | EH01 |
| Journal: | Algorithmica |
| Volume: | 32 |
| Pages: | 467-473 |
| 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 maximum-flow algorithm of Goldberg and Rao, the binary blocking flow algorithm. |
| Remarks: | DOI:10.1007/s00453-001-0082-y, Online publication: 23 November 2001 |
| Resources: | [BibTeX] |
