Finding a feasible flow in a strongly connected network |
| |
| Authors: | Bernhard Haeupler Robert E Tarjan |
| |
| Institution: | a Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ 08540-5233, United States
b HP Laboratories, Palo Alto CA, United States |
| |
| Abstract: | We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor. |
| |
| Keywords: | Combinatorial algorithms Network flow Feasible flow Strongly connected network Maximum flow |
| 本文献已被 ScienceDirect 等数据库收录！ |
