Algorithms and complexity analysis for some flow problems |
| |
Authors: | Edith Cohen Nimrod Megiddo |
| |
Affiliation: | (1) Present address: Currently at AT&T Bell Laboratories, 600 Mountain Avenue, 07974 Murray Hill, NJ, USA;(2) IBM Almaden Research Center, 95120-6099 San Jose, CA, USA;(3) School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be -complete. It is shown that the existence of a strongly polynomial-time algorithm for any of these problems implies the existence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some parametric flow problems are given, when the number of parameters is fixed. These algorithms are applicable to constrained flow problems when the number of additional constraints is fixed.Work on the paper was done while at Stanford University and IBM Almaden Research Center. This research was partially supported by NSF PYI Grant CCR-8858097. |
| |
Keywords: | Parametric flow Constrained flow Strongly polynomial time |
本文献已被 SpringerLink 等数据库收录! |
|