Skip to main content
SpringerLink
Log in

On the structure of all minimum cuts in a network and applications

  • Chapter
  • First Online:
Combinatorial Optimization II

Part of the book series: Mathematical Programming Studies ((MATHPROGRAMM,volume 13))

Abstract

This paper presents a characterization of all minimum cuts, separating a source from a sink in a network. A binary relation is associated with any maximum flow in this network, and minimum cuts are identified with closures for this relation. As a consequence, finding all minimum cuts reduces to a straightforward enumeration. Applications of this results arise in sensitivity and parametric analyses of networks, the vertex packing and maximum closure problems, in unconstrained pseudo-boolean optimization and project selection, as well as in other areas of application of minimum cuts.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. D. Adolphson and T.C. Hu, “Optimal linear ordering”, Society for Industrial and Applied Mathematics Journal of Applied Mathematics 25 (1973) 403–423.

    Article  MATH  MathSciNet  Google Scholar 

  2. M.L. Balinski, “On a selection problem”, Management Science 17 (1970) 230–231.

    Article  MATH  MathSciNet  Google Scholar 

  3. D.W. Davies and D.L.A. Barber, Communication networks for computers (Wiley, Chichester, Great Britain, 1973).

    Google Scholar 

  4. L.R. Ford and D.R. Fulkerson, Flows in networks (Princeton University Press, Princeton, NJ, 1962).

    MATH  Google Scholar 

  5. R.L. Francis and P.B. Saunders, “EVACNET: Prototype network optimization models for building evacuation”, Report NBSIR 79-1738, National Bureau of Standards, Washington, DC (1979).

    Google Scholar 

  6. G. Gratzer, Lattice Theory: first concepts and distributive lattices (W.M. Freeman and Co., San Francisco, CA., 1971).

    Google Scholar 

  7. A.L. Gutjahr and G.J. Nemhauser, “An algorithm for the line balancing problem”, Management Science 11 (1964) 308–315.

    Article  MathSciNet  Google Scholar 

  8. Han Chang, “Funding the n most vital nodes in a flow network”, Dissertation. University of Texas at, Arlington, TX (1972).

    Google Scholar 

  9. T.C. Hu, Integer programming and network flows (Addison-Wesley, Reading, MA, 1970).

    Google Scholar 

  10. T.C. Hu, “Optimum communication spanning trees”, Society for Industrial and Applied Mathematics Journal of Computing 3 (1974) 188–195.

    MATH  Google Scholar 

  11. E.L. Lawler, “Efficient implementation of dynamic programming algorithms for sequencing problems”, Report bw 106/79, Stitchting Mathematisch Centrum, Amsterdam, The Netherlands (1979).

    MATH  Google Scholar 

  12. S.M. Lubore, H.D. Ratliff and G.T. Sicilia, “Determining the most vital link in a flow network”, Naval Research Logistic Quarterly 18 (1971) 497–502.

    Article  MathSciNet  Google Scholar 

  13. L.F. McGinnis and H.L.W. Nuttle, “The project coordinators’ problem”, Omega 6 (1978) 325–330.

    Article  Google Scholar 

  14. E. Minieka, Optimization algorithms for networks and graphs (Marcel Dekker Inc., New York, 1978).

    MATH  Google Scholar 

  15. G.L. Nemhauser and L.E. Trotter, “Vertex packings: structural properties and algorithms”, Mathematical Programming 8 (1975) 232–248.

    Article  MATH  MathSciNet  Google Scholar 

  16. S. Phillips Jr. and M.E. Dessouky, “Solving the project time/cost tradeoff problem using the minimal cut concept”, Management Science 24 (1977) 393–400.

    Article  MATH  Google Scholar 

  17. J.-C. Picard, “Maximal closure of a graph and application to combinatorial problems”, Management Science 22 (1976) 1268–1272.

    Article  MATH  MathSciNet  Google Scholar 

  18. J.-C. Picard and M. Queyranne, “Vertex packings: (VLP)—reductions through alternate labeling”, Technical report EP75-R-47, Ecole Polytechnique de Montréal, Que., Canada (1975).

    Google Scholar 

  19. J.-C. Picard and M. Queyranne, “On the integer-valued variables in the linear vertex packing problem”, Mathematical Programming 12 (1977) 97–101.

    Article  MATH  MathSciNet  Google Scholar 

  20. J.-C. Picard and M. Queyranne, “Networks graphs and some nonlinear 0–1 programming problems”, Technical report EP77-R-32, Ecole Polytechnique de Montréal, Que., Canada (1977).

    Google Scholar 

  21. J.-C. Picard and M. Queyranne, “Selected applications of the maximum flow and minimum cut problems”, Tech. Rept. EP79-R-35, Ecole Polytechnique de Montréal, Montréal, Qué., Canada (1979).

    Google Scholar 

  22. J.-C. Picard and H.D. Ratliff, “Minimum cuts and related problems”, Networks 5 (1975) 357–370.

    Article  MATH  MathSciNet  Google Scholar 

  23. M. Queyranne, “Anneaux achevés d’ensembles et préordres”, Technical report EP77-R-14, Ecole de Montréal, Que., Canada (1977).

    Google Scholar 

  24. J.M.W. Rhys, “A selection problem of shared fixed costs and network flows”, Management Science 17 (1970) 200–207.

    Article  MATH  Google Scholar 

  25. L. Schrage and K.R. Baker, “Dynamic programming solution of sequencing problems with precedence constraints”, Operations Research 26 (1978) 444–449.

    Article  MATH  Google Scholar 

  26. G.T. Sicilia, “Finding the n most vital links in a network”, Dissertation, University of Florida, Gainesville, FL, (1970).

    Google Scholar 

  27. D.M. Topkis, “Monotone minimum node-cuts in capacitated networks”, Research report ORC 70-39, University of California, Berkeley, CA, (1970).

    Google Scholar 

  28. R. Wollmer, “Sensitivity analysis in networks”, Technical repoot ORC 65-8, University of California, Berkeley, CA, (1965).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Ecole Polytechnique, Thiès, Sénégal

    Jean-Claude Picard

  2. University of Houston, Houston, TX, USA

    Maurice Queyranne

Authors
  1. Jean-Claude Picard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maurice Queyranne
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

V. J. Rayward-Smith

Rights and permissions

Reprints and permissions

Copyright information

© 1980 The Mathematical Programming Society

About this chapter

Cite this chapter

Picard, JC., Queyranne, M. (1980). On the structure of all minimum cuts in a network and applications. In: Rayward-Smith, V.J. (eds) Combinatorial Optimization II. Mathematical Programming Studies, vol 13. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120902

Download citation

  • DOI: https://doi.org/10.1007/BFb0120902

  • Received:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00803-0

  • Online ISBN: 978-3-642-00804-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation