{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T05:10:13Z","timestamp":1716613813873},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,4,1]],"date-time":"1996-04-01T00:00:00Z","timestamp":828316800000},"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":[[1996,4]]},"DOI":"10.1007\/bf01961544","type":"journal-article","created":{"date-parts":[[2005,7,29]],"date-time":"2005-07-29T16:13:26Z","timestamp":1122653606000},"page":"351-372","source":"Crossref","is-referenced-by-count":8,"title":["A paradigm for listing (s, t)-cuts in graphs"],"prefix":"10.1007","volume":"15","author":[{"given":"J. S.","family":"Provan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. R.","family":"Shier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01961544_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1109\/TR.1982.5221285","volume":"31","author":"U. Abel","year":"1982","unstructured":"U. Abel and R. Bicker, Determination of all minimal cut-sets between a vertex pair in an undirected graph,IEEE Trans. Reliability 31 (1982), 167\u2013171.","journal-title":"IEEE Trans. Reliability"},{"key":"BF01961544_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01961544_CR3","unstructured":"M. R. Anderson, Null nonterminal insertion inLR(k) grammars, Technical Report CSE-TR-49-90, Department of Electrical Engineering and Computer Science, University of Michigan, 1990."},{"key":"BF01961544_CR4","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/net.3230130210","volume":"13","author":"M. O. Ball","year":"1983","unstructured":"M. O. Ball and J. S. Provan, Calculating bounds on reachability and connectedness in stochastic networks,Networks 13 (1983), 253\u2013278.","journal-title":"Networks"},{"key":"BF01961544_CR5","unstructured":"M. O. Ball and J. S. Provan, ComputingK-terminal reliability in time polynomial in the number of (s, K)-quasicuts,Proc. Fourth Army Conference on Applied Mathematics and Computing, 1987, pp. 901\u2013907."},{"key":"BF01961544_CR6","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1080\/00401706.1970.10488728","volume":"12","author":"M. Bellmore","year":"1970","unstructured":"M. Bellmore and P. A. Jensen, An implicit enumeration scheme for proper cut generation,Technometrics 12 (1970), 775\u2013788.","journal-title":"Technometrics"},{"key":"BF01961544_CR7","volume-title":"The Combinatorics of Network Reliability","author":"C. J. Colbourn","year":"1987","unstructured":"C. J. Colbourn,The Combinatorics of Network Reliability, Oxford University Press, New York, 1987."},{"key":"BF01961544_CR8","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/TCT.1973.1083657","volume":"20","author":"L. Fratta","year":"1973","unstructured":"L. Fratta and U. G. Montanari, A Boolean algebra method for computing the terminal reliability in a communication network,IEEE Trans. Circuit Theory 20 (1973), 203\u2013211.","journal-title":"IEEE Trans. Circuit Theory"},{"key":"BF01961544_CR9","first-page":"147","volume":"8","author":"M. L. Gardner","year":"1985","unstructured":"M. L. Gardner, An algorithm to aid in the design of large scale networks,Large Scale Systems 8 (1985), 147\u2013156.","journal-title":"Large Scale Systems"},{"key":"BF01961544_CR10","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R. E. Gomory","year":"1961","unstructured":"R. E. Gomory and T. C. Hu, Multi-terminal network flows,SIAM J. Appl. Math. 9 (1961), 551\u2013570.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01961544_CR11","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 (1990), 143\u2013155.","journal-title":"SIAM J. Comput."},{"key":"BF01961544_CR12","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF01908632","volume":"10","author":"D. Gusfield","year":"1993","unstructured":"D. Gusfield and D. Naor, Extracting maximal information about sets of minimum cuts,Algorithmica 10 (1993), 64\u201389.","journal-title":"Algorithmica"},{"key":"BF01961544_CR13","volume-title":"Graph Theory","author":"F. Harary","year":"1971","unstructured":"F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1971."},{"key":"BF01961544_CR14","doi-asserted-by":"crossref","unstructured":"D. Harel, A linear time algorithm for finding dominators in flow graphs and related problems (extended abstract),Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 185\u2013194.","DOI":"10.1145\/22145.22166"},{"key":"BF01961544_CR15","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 (1988), 535\u2013542.","journal-title":"Math. Oper. Res."},{"key":"BF01961544_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1109\/TR.1969.5216346","volume":"18","author":"P. A. Jensen","year":"1969","unstructured":"P. A. Jensen and M. Bellmore, An algorithm to determine the reliability of a complex system,IEEE Trans. Reliability 18 (1969), 169\u2013174.","journal-title":"IEEE Trans. Reliability"},{"key":"BF01961544_CR17","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1002\/net.3230230604","volume":"23","author":"A. Kanevsky","year":"1993","unstructured":"A. Kanevsky, Finding all minimum size separating vertex sets in a graph,Networks 23 (1993), 533\u2013541.","journal-title":"Networks"},{"key":"BF01961544_CR18","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1287\/opre.33.6.1389","volume":"33","author":"V. G. Kulkarni","year":"1985","unstructured":"V. G. Kulkarni and J. S. Provan, An improved implementation of conditional Monte Carlo estimation of path lengths in stochastic networks,Oper. Res. 33 (1985), 1389\u20131393.","journal-title":"Oper. Res."},{"key":"BF01961544_CR19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E. L. Lawler","year":"1978","unstructured":"E. L. Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints,Ann. Discrete Math. 2 (1978), 75\u201390.","journal-title":"Ann. Discrete Math."},{"key":"BF01961544_CR20","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and L. E. Trotter, Vertex packings: structural properties and algorithms,Math. Programming 8 (1975), 232\u2013248.","journal-title":"Math. Programming"},{"key":"BF01961544_CR21","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","volume":"13","author":"J. C. Picard","year":"1980","unstructured":"J. C. Picard and 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":"BF01961544_CR22","first-page":"394","volume":"20","author":"J. C. Picard","year":"1982","unstructured":"J. C. Picard and M. Queyranne, Selected applications of minimum cuts in networks,INFOR 20 (1982), 394\u2013422.","journal-title":"INFOR"},{"key":"BF01961544_CR23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01582058","volume":"63","author":"J. S. Provan","year":"1994","unstructured":"J. S. Provan, Efficient enumeration of the vertices of polyhedra associated with network LP's,Math. Programming 63 (1994), 47\u201364.","journal-title":"Math. Programming"},{"key":"BF01961544_CR24","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1002\/net.3230190303","volume":"19","author":"J. S. Provan","year":"1989","unstructured":"J. S. Provan and V. G. Kulkarni, Exact cuts in networks,Networks 19 (1989), 281\u2013289.","journal-title":"Networks"},{"key":"BF01961544_CR25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF02592076","volume":"39","author":"A. Ramanathan","year":"1987","unstructured":"A. Ramanathan and C. J. Colbourn, Counting almost minimum cutsets with reliability applications,Math. Programming 39 (1987), 253\u2013261.","journal-title":"Math. Programming"},{"key":"BF01961544_CR26","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"R. C. Read","year":"1975","unstructured":"R. C. Read and R. E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees,Networks 5 (1975), 237\u2013252.","journal-title":"Networks"},{"key":"BF01961544_CR27","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198533863.001.0001","volume-title":"Network Reliability and Algebraic Structures","author":"D. R. Shier","year":"1991","unstructured":"D. R. Shier,Network Reliability and Algebraic Structures, Clarendon Press, Oxford, 1991."},{"key":"BF01961544_CR28","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/0378-4754(79)90007-7","volume":"21","author":"C. E. Sigal","year":"1979","unstructured":"C. E. Sigal, A. A. B. Pritsker, and J. J. Solberg, The use of cutsets in Monte Carlo analysis of stochastic networks,Math. Comput. Simulation 21 (1979), 376\u2013384.","journal-title":"Math. Comput. Simulation"},{"key":"BF01961544_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 (1986), 317\u2013320.","journal-title":"Oper. Res. Lett."},{"key":"BF01961544_CR30","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/0203006","volume":"3","author":"R. E. Tarjan","year":"1974","unstructured":"R. E. Tarjan, Finding dominators in directed graphs,SIAM J. Comput. 3 (1974), 62\u201389.","journal-title":"SIAM J. Comput."},{"key":"BF01961544_CR31","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1145\/322217.322220","volume":"27","author":"S. Tsukiyama","year":"1980","unstructured":"S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi, An algorithm to enumerate all cutsets of a graph in linear time per cutset,J. Assoc. Comput. Mach. 27 (1980), 619\u2013632.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01961544_CR32","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0016-0032(59)90487-9","volume":"268","author":"O. Wing","year":"1959","unstructured":"O. Wing and W. H. Kim, The path matrix and switching functions,J. Franklin Inst. 268 (1959), 251\u2013269.","journal-title":"J. Franklin Inst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01961544.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01961544\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01961544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T06:30:50Z","timestamp":1706423450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01961544"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["BF01961544"],"URL":"https:\/\/doi.org\/10.1007\/bf01961544","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}