Abstract
In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in Gallo, Grigoriadis, and Tarjan (1989), and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property (Arai, Ueno, and Kajitani, 1993). A consequence is that the corresponding parametric maximum flow value function has at most n −1 breakpoints. All the minimum cut capacities can therefore be computed by O(1) maximum flow computations.
We will show then that, given O(n) increasing values of the parameter, it is possible to compute the corresponding maximum flows by O(1) maximum flow computations, by suitably extending Goldberg and Tarjan’s maximum flow algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network Flows: Theory, Algorithms and Applications. Englewood Cliffs, NJ: Prentice Hall.
Arai, T., S. Ueno, and Y. Kajitani. (1993). “Generalization of a Theorem on the Parametric Maximum Flow Problem.” Discrete Applied Mathematics, 41, 69–74.
Brumelle, S., D. Granot, and L. Liu. (2002). “Ordered Optimal Solutions and Parametric Minimum Cut Problems.” Working paper.
Carstensen, P.J. (1983). “Complexity of Some Parametric Integer and Network Programming Problems.” Mathematical Programming, 26, 64–75.
Ford Jr., L.R. and D.R. Fulkerson. (1962). Flows in Networks. Princeton, NJ: Princeton University Press.
Gallo, G., M.D. Grigoriadis, and R.E. Tarjan. (1989). “A Fast Parametric Maximum Flow Algorithm and Applications.” SIAM J. Comp., 18(1), 30–55.
Goldberg, A.V. and R.E. Tarjan. (1986). “A New Approach to the Maximum Flow Problem.” Proc. 18th Annual ACM Symposium on Theory of Computing, 136–146.
Goldberg, A.V. and R.E. Tarjan. (1988). “A New Approach to the Maximum Flow Problem.” JACM, 35(4), 921–940.
Gusfield, D. and C. Martel. (1992). “A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications.” Algorithmica, 7, 499–519.
McCormick, S.T. (1999). “Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow.” Operations Research, 47(5), 744–756.
Sleator, D.D. and R.E. Tarjan. (1983). “A Data Structure for Dynamic Trees.” J. Comput. System Sci., 24, 362–391.
Sleator, D.D. and R.E. Tarjan. (1985). “Self-Adjusting Binary Search Trees.” JACM, 32, 652–686.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Scutellà, M.G. A note on the parametric maximum flow problem and some related reoptimization issues. Ann Oper Res 150, 231–244 (2007). https://doi.org/10.1007/s10479-006-0155-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0155-z