Abstract
Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n3+kn2) total time, provided that the capacity changes are made “in order.” Using dynamic trees their time bound isO(nm log(n2/m)+km log(n2/m)). We show how to reduce the total time, using a simple algorithm, to O(n3+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n2/m)+kn log(n2/m)). We further reduce the total time toO(n 2√m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not “in order,” provided we only need the minimum cuts; if the flows are required then the times are respectively O(n3+km) and O(n2√m). We illustrate the utility of these results by applying them to therectilinear layout problem.
Similar content being viewed by others
References
J. Cheriyan and S. N. Maheshwari. Analysis of preflow push algorithms for maximum network flow.SIAM Journal on Computing, 18:1057–1086, 1989.
T. Y. Cheung. Multifacility location problem with rectilinear distance by the minimum-cut approach.ACM Transactions on Mathematical Software, 6:549–561, 1980.
L. R. Ford and D. R. Fulkerson.Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
G. Gallo, M. Grigoriadis, and R. E. Tarjan. A fast parametric network flow algorithm.SIAM Journal on Computing, 18:30–55, 1989.
A. V. Goldberg, É. Tardos, and R. E. Tarjan. Network flow algorithms. In:Paths, Flows, and VLSI-Design (B. Korte, L. Lovász, and A. Schrijver, eds.), Springer-Verlag, New York, 1990.
A. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem.Journal of the Association for Computing Machinery, 4:136–146, 1988.
D. Gusfield. Computing the strength of a graph.SIAM Journal on Computing, 20:639–654, 1991.
D. Gusfield and R. Irving.The Stable Marriage Problem: Structure and Algorithms. MIT press, Cambridge, MA, 1989.
D. Gusfield and R. W. Irving. Parametric stable marriage and minimum cuts.Information Processing Letters, 30:255–259, 1989.
D. Gusfield and C. Martel. A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications. Technical Report CSE-89-21, University of California, Davis, CA, 1989.
D. Gusfield and C. Martel. A fast algorithm for the generalized parametric minimum cut problem and applications.Algorithmica, 7:499–519, 1992.
E. L. Lawler.Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976.
C. Martel. A comparison of phase and non-phase network algorithms.Networks, 19:691–705, 1989.
J. Picard and H. Ratliff. A cut approach to the rectilinear distance facility location problem.Operations Research, 26:422–433, 1978.
R. E. Tarjan.Data Structures and Network Algorithms. SIAM, Philadelphia, PA, 1983.
V. A. Trubin. Effective algorithm for the weber problem with a rectangular metric.Cybernetics, 14:874–878, 1978.
L. Tunçel. On the Complexity of Preflow-Push Algorithms for Maximum Flow Problems. Technical Report OR-901, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1990.
Author information
Authors and Affiliations
Additional information
Communicated by Harold N. Gabow.
The research of Dan Gusfield was partially supported by Grants CCR-8803704 and CCR-9103937 from the National Science Foundation. The research of Éva Tardos was partially supported by a David and Lucile Packard Fellowship, an NSF Presidential Young Investigator Fellowship, a Research Fellowship of the Sloan Foundation, and by NSF, DARPA, and ONR through Grant DMS89-20550 from the National Science Foundation.
Rights and permissions
About this article
Cite this article
Gusfield, D., Tardos, É. A faster parametric minimum-cut algorithm. Algorithmica 11, 278–290 (1994). https://doi.org/10.1007/BF01240737
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01240737