{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:51Z","timestamp":1771036371716,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,2,14]],"date-time":"2009-02-14T00:00:00Z","timestamp":1234569600000},"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":[[2010,3]]},"DOI":"10.1007\/s00453-009-9284-5","type":"journal-article","created":{"date-parts":[[2009,2,16]],"date-time":"2009-02-16T04:57:16Z","timestamp":1234760236000},"page":"297-312","source":"Crossref","is-referenced-by-count":15,"title":["Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing Weights"],"prefix":"10.1007","volume":"56","author":[{"given":"Li-Pu","family":"Yeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Biing-Feng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,2,14]]},"reference":[{"key":"9284_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications, 1st edn. Prentice-Hall, Englewood Cliffs (1993)","edition":"1"},{"key":"9284_CR2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0167-6377(97)00043-6","volume":"21","author":"M. Burlet","year":"1997","unstructured":"Burlet, M., Goldschmidt, O.: A new and improved algorithm for the 3-cut problem. Oper. Res. Lett. 21, 225\u2013227 (1997)","journal-title":"Oper. Res. Lett."},{"key":"9284_CR3","unstructured":"Chekuri, C.S., Goldberg, A.V., Karger, D.R., Levine, M.S., Stein, C.: Experimental study of minimum cut algorithms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 324\u2013333 (1997)"},{"key":"9284_CR4","first-page":"290","volume-title":"Studies in Discrete Optimization","author":"E.A. Dinits","year":"1976","unstructured":"Dinits, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimal weighted cuts in a graph. In: Fridman, A.A. (ed.) Studies in Discrete Optimization, pp. 290\u2013306. Nauka, Moscow (1976) (Original article in Russian. Translation available from NTC-National Translations Center, Library of Congress, Cataloging Distribution Service, Washington DC 20541, USA (NTC 89-20265))"},{"key":"9284_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/jagm.1999.1039","volume":"33","author":"L. Fleischer","year":"1999","unstructured":"Fleischer, L.: Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time. J. Algorithms 33, 51\u201372 (1999)","journal-title":"J. Algorithms"},{"key":"9284_CR6","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. ACM 35, 921\u2013940 (1988)","journal-title":"J. ACM"},{"key":"9284_CR7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: Polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19, 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"9284_CR8","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9, 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9284_CR9","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J. Hao","year":"1994","unstructured":"Hao, J., Orlin, J.B.: A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms 17, 424\u2013446 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"9284_CR10","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/s004539910009","volume":"26","author":"M. J\u00fcnger","year":"2000","unstructured":"J\u00fcnger, M., Rinaldi, G.: Practical performance of efficient minimum cut algorithms. Algorithmica 26(1), 172\u2013195 (2000)","journal-title":"Algorithmica"},{"key":"9284_CR11","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/s00453-001-0070-2","volume":"32","author":"Y. Kamidoi","year":"2002","unstructured":"Kamidoi, Y., Wakabayashi, S., Yoshida, N.: A divide-and-conquer approach to the minimum k-way cut problem. Algorithmica 32, 262\u2013276 (2002)","journal-title":"Algorithmica"},{"key":"9284_CR12","first-page":"1315","volume":"36","author":"Y. Kamidoi","year":"2006","unstructured":"Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding all minimum k-way cuts. SIAM J. Comput. 36, 1315\u20131327 (2006)","journal-title":"SIAM J. Comput."},{"key":"9284_CR13","doi-asserted-by":"crossref","unstructured":"Kapoor, S.: On minimum 3-cuts and approximating k-cuts using cut trees. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference, pp. 132\u2013146 (1996)","DOI":"10.1007\/3-540-61310-2_11"},{"key":"9284_CR14","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1137\/S0097539796298340","volume":"29","author":"D.R. Karger","year":"1999","unstructured":"Karger, D.R.: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J. Comput. 29, 492\u2013514 (1999)","journal-title":"SIAM J. Comput."},{"key":"9284_CR15","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47, 46\u201376 (2000)","journal-title":"J. ACM"},{"key":"9284_CR16","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM 43, 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"9284_CR17","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BF01074775","volume":"22","author":"A.V. Karzanov","year":"1986","unstructured":"Karzanov, A.V., Timofeev, E.A.: Efficient algorithms for finding all minimal edge cuts of a nonoriented graph. Cybernetics 22, 156\u2013162 (1986) (Translated from Kibernetika 2, 8\u201312 (1986))","journal-title":"Cybernetics"},{"key":"9284_CR18","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1006\/jagm.1994.1044","volume":"17","author":"V. King","year":"1994","unstructured":"King, V., Rao, S., Tarjan, R.E.: A faster deterministic maximum flow algorithm. J. Algorithms 17, 447\u2013474 (1994)","journal-title":"J. Algorithms"},{"key":"9284_CR19","unstructured":"Levine, M.S.: Faster randomized algorithms for computing minimum {3, 4, 5, 6}-way cuts. In: Proceedings of the Eleventh ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 735\u2013742 (2000)"},{"key":"9284_CR20","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing the edge-connectivity of multigraphs and capacitated graphs. SIAM J. Discrete Math. 5, 54\u201366 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9284_CR21","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/PL00011383","volume":"88","author":"H. Nagamochi","year":"2000","unstructured":"Nagamochi, H., Ibaraki, T.: A fast algorithm for computing minimum 3-way and 4-way cuts. Math. Program. 88, 507\u2013520 (2000)","journal-title":"Math. Program."},{"key":"9284_CR22","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01582226","volume":"67","author":"H. Nagamochi","year":"1994","unstructured":"Nagamochi, H., Ono, T., Ibaraki, T.: Implementing an efficient minimum capacity cut algorithm. Math. Program. 67, 325\u2013341 (1994)","journal-title":"Math. Program."},{"key":"9284_CR23","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1137\/S0895480194271323","volume":"10","author":"H. Nagamochi","year":"1997","unstructured":"Nagamochi, H., Nishimura, K., Ibaraki, T.: Computing all small cuts in undirected networks. SIAM J. Discrete Math. 10, 469\u2013481 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"9284_CR24","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1009804919645","volume":"4","author":"H. Nagamochi","year":"2000","unstructured":"Nagamochi, H., Katayama, S., Ibaraki, T.: A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. J. Comb. Optim. 4, 151\u2013169 (2000)","journal-title":"J. Comb. Optim."},{"key":"9284_CR25","first-page":"179","volume":"E86-D","author":"H. Nagamochi","year":"2003","unstructured":"Nagamochi, H., Nakamura, S., Ishii, T.: Constructing a cactus for minimum cuts of a graph in O(mn+n 2log\u2009n) time and O(m) space. IEICE Trans. Inf. Syst. E86-D, 179\u2013185 (2003)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"9284_CR26","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","volume":"13","author":"J.C. Picard","year":"1980","unstructured":"Picard, J.C., Queyranne, M.: On the structure of all minimum cuts in a network and applications. Math. Program. Study 13, 8\u201316 (1980)","journal-title":"Math. Program. Study"},{"key":"9284_CR27","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Minimum k-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 159\u2013165 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"9284_CR28","doi-asserted-by":"crossref","unstructured":"Vazirani, V., Yannakakis, M.: Suboptimal cuts: their enumeration, weight, and number. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, pp. 366\u2013377 (1992)","DOI":"10.1007\/3-540-55719-9_88"},{"key":"9284_CR29","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1023\/A:1011620607786","volume":"5","author":"L. Zhao","year":"2001","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Approximating the minimum k-way cut in a graph via minimum 3-way cuts. J. Comb. Optim. 5, 397\u2013410 (2001)","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9284-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9284-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9284-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:03Z","timestamp":1559123103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9284-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,14]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["9284"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9284-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,14]]}}}