{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:16:52Z","timestamp":1772468212516,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,7,1]],"date-time":"1993-07-01T00:00:00Z","timestamp":741484800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,7]]},"DOI":"10.1007\/bf01908632","type":"journal-article","created":{"date-parts":[[2005,7,22]],"date-time":"2005-07-22T15:56:24Z","timestamp":1122047784000},"page":"64-89","source":"Crossref","is-referenced-by-count":18,"title":["Extracting maximal information about sets of minimum cuts"],"prefix":"10.1007","volume":"10","author":[{"given":"Dan","family":"Gusfield","sequence":"first","affiliation":[]},{"given":"Dalit","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01908632_CR1","volume-title":"Flow Algorithms","author":"G. M. Adelson-Velskii","year":"1976","unstructured":"G. M. Adelson-Velskii, E. A. Dinits, A. V. Karzanov,Flow Algorithms, Nauka, Moscow, 1976 (in Russian)."},{"key":"BF01908632_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01908632_CR3","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/net.3230130210","volume":"13","author":"M. O. Ball","year":"1983","unstructured":"M. O. Ball, J. S. Provan, Calculating Bounds on Reachability and Connectedness in Stochastic Networks,Networks,13 (1983), 253\u2013278.","journal-title":"Networks"},{"key":"BF01908632_CR4","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/net.1975.5.3.253","volume":"5","author":"R. E. Bixby","year":"1975","unstructured":"R. E. Bixby, The Minimum Number of Edges and Vertices in a Graph with Edge Connectivityn andm n-Bonds,Networks,5 (1975), 253\u2013298.","journal-title":"Networks"},{"key":"BF01908632_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230180102","volume":"18","author":"C. J. Colbourn","year":"1988","unstructured":"C. J. Colbourn, D. D. Harms, Bounding All-Terminal Reliability in Computer Networks,Networks,18 (1988), 1\u201312.","journal-title":"Networks"},{"key":"BF01908632_CR6","first-page":"290","volume-title":"Studies in Discrete Optimization","author":"E. A. Dinits","year":"1976","unstructured":"E. A. Dinits, A. V. Karzanov, M. L. Lomosonov, On the Structure of a Family of Minimal Weighted Cuts in a Graph, inStudies in Discrete Optimization (A. A. Fridman, ed.), Nauka, Moscow, 1976, pp. 290\u2013306 (in Russian)."},{"key":"BF01908632_CR7","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1002\/net.3230140211","volume":"14","author":"A. H. Esfahanian","year":"1984","unstructured":"A. H. Esfahanian, S. L. Hakimi, On Computing the Connectivities of Graphs and Digraphs,Networks,14 (1984), 355\u2013366.","journal-title":"Networks"},{"key":"BF01908632_CR8","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"S. Even, R. E. Tarjan, Network Flow and Testing Graph Connectivity,SIAM J. Comput.,4 (1975), 507\u2013518.","journal-title":"SIAM J. Comput."},{"key":"BF01908632_CR9","volume-title":"Flows in Networks","author":"L. R. Ford","year":"1962","unstructured":"L. R. Ford, D. R. Fulkerson,Flows in Networks, Princeton University Press, Princeton, NJ, 1962."},{"key":"BF01908632_CR10","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"G. Gallo, M. D. Grigoriadis, R. E. Tarjan, A Fast Parametric Maximum Flow Algorithm,SIAM J. Comput.,18 (1989), 30\u201355.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"BF01908632_CR11","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A. V. Goldberg","year":"1988","unstructured":"A. V. Goldberg, R. E. Tarjan, A New Approach to the Maximum Flow Problem,J. Assoc. Comput. Mach.,35(4) (1988), 921\u2013940.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01908632_CR12","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R. E. Gomory","year":"1961","unstructured":"R. E. Gomory, T. C. Hu, Multi-Terminal Network Flows,SIAM J. Appl. Math.,9 (1961), 551\u2013560.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01908632_CR13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0166-218X(86)90079-X","volume":"13","author":"F. Granot","year":"1986","unstructured":"F. Granot, R. Hassin, Multi-Terminal Maximum Flows in Node-Capacitated Networks,Discrete Appl. Math.,13 (1986), 157\u2013163.","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"BF01908632_CR14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","volume":"16","author":"D. Gusfield","year":"1987","unstructured":"D. Gusfield, Three Fast Algorithms for Four Problems in Stable Marriage,SIAM J. Comput.,16(1) (1987), 111\u2013128.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"BF01908632_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0219009","volume":"19","author":"D. Gusfield","year":"1990","unstructured":"D. Gusfield, Very Simple Methods for All Pairs Network Flow Analysis,SIAM J. Comput.,19(1) (1990), 143\u2013155.","journal-title":"SIAM J. Comput."},{"key":"BF01908632_CR16","volume-title":"Technical Report CSE-88-14","author":"D. Gusfield","year":"1988","unstructured":"D. Gusfield, D. Naor, Extracting Maximal Information About Sets of Minimum Cuts, Technical Report CSE-88-14, Computer Science Division, University of California, Davis, CA, September 1988."},{"issue":"5","key":"BF01908632_CR17","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1002\/net.3230210503","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"D. Gusfield, D. Naor, Efficient Algorithms for Generalized Cut Trees,Networks,21(5) (1991), 505\u2013520. Also inProc. First Annual ACM-SIAM Symposium on Discrete Algorithms, January 1990, San Francisco, CA, pp. 422\u2013433.","journal-title":"Networks"},{"issue":"4","key":"BF01908632_CR18","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1287\/moor.13.4.535","volume":"13","author":"R. Hassin","year":"1988","unstructured":"R. Hassin, Solution Bases of Multi-Terminal Cut Problems,Math. Oper. Res.,13(4) (1988), 535\u2013542.","journal-title":"Math. Oper. Res."},{"key":"BF01908632_CR19","volume-title":"Technical Report TAMU-89-10","author":"A. Kanevsky","year":"1989","unstructured":"A. Kanevsky, Graphs with Odd and Even Edge Connectivity are Inherently Different, Technical Report TAMU-89-10, Texas A&M University, College Station, TX, June 1989."},{"issue":"2","key":"BF01908632_CR20","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BF01074775","volume":"22","author":"A. V. Karzanov","year":"1986","unstructured":"A. V. Karzanov, E. A. Timofeev, Efficient Algorithm for Finding All Minimal Edge Cuts of a Nonoriented Graph,Cybernetics,22(2) (1986), 156\u2013162. (Translated fromKibernetika, no. 2 (1986), 8\u201312.)","journal-title":"Cybernetics"},{"issue":"1","key":"BF01908632_CR21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0196-6774(89)90024-2","volume":"10","author":"Y. Mansour","year":"1989","unstructured":"Y. Mansour, B. Schieber, Finding the Edge Connectivity of Directed Graphs,J. Algorithms,10(1) (1989), 76\u201385.","journal-title":"J. Algorithms"},{"key":"BF01908632_CR22","doi-asserted-by":"crossref","unstructured":"D. Matula, Determining Edge Connectivity inO(nm), Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, October 1987, Los Angeles, CA, pp. 249\u2013251.","DOI":"10.1109\/SFCS.1987.19"},{"key":"BF01908632_CR23","volume-title":"Ph.D. Thesis","author":"D. Naor","year":"1991","unstructured":"D. Naor, The Structure of Minimum Cuts with Applications to Edge-Augmentation, Ph.D. Thesis, University of California, Davis, CA, 1991."},{"key":"BF01908632_CR24","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","volume":"13","author":"J. C. Picard","year":"1980","unstructured":"J. C. Picard, M. Queyranne, On the Structure of All Minimum Cuts in a Network and Applications,Math. Programming Stud.,13 (1980), 8\u201316.","journal-title":"Math. Programming Stud."},{"key":"BF01908632_CR25","first-page":"394","volume":"20","author":"J. C. Picard","year":"1982","unstructured":"J. C. Picard, M. Queyranne, Selected Applications of Minimum Cuts in Networks,Inform-Canad. J. Oper. Res. Inform. Process.,20 (1982), 394\u2013422.","journal-title":"Inform-Canad. J. Oper. Res. Inform. Process."},{"key":"BF01908632_CR26","volume-title":"Technical Report UNC\/OR TR91-3","author":"J. S. Provan","year":"1991","unstructured":"J. S. Provan, D. R. Shier, A Paradigm for Listing (s-t) Cuts in Graphs, Technical Report UNC\/OR TR91-3, Department of Operations Research, University of North Carolina, Chapel Hill, NC, February 1991."},{"key":"BF01908632_CR27","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF02592076","volume":"39","author":"A. Ramanathan","year":"1987","unstructured":"A. Ramanathan, C. J. Colbourn, Counting Almost Minimum Cutsets with Reliability Applications,Math. Programming,39 (1987), 253\u2013261.","journal-title":"Math. Programming"},{"key":"BF01908632_CR28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1137\/0208019","volume":"8","author":"C. P. Schnoor","year":"1979","unstructured":"C. P. Schnoor, Bottlenecks and Edge Connectivity in Unsymmetrical Networks,SIAM J. Comput.,8 (1979), 265\u2013274.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"BF01908632_CR29","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0167-6377(86)90071-4","volume":"5","author":"G. Steiner","year":"1986","unstructured":"G. Steiner, An Algorithm to Generate the Ideals of a Partial Order,Oper. Res. Lett.,5(6) (1986), 317\u2013320.","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01908632.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01908632\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01908632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T09:14:06Z","timestamp":1586337246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01908632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["BF01908632"],"URL":"https:\/\/doi.org\/10.1007\/bf01908632","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}