{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T11:41:59Z","timestamp":1773402119088,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2010,12,21]],"date-time":"2010-12-21T00:00:00Z","timestamp":1292889600000},"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":[[2012,4]]},"DOI":"10.1007\/s00453-010-9483-0","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T16:35:54Z","timestamp":1292862954000},"page":"787-806","source":"Crossref","is-referenced-by-count":14,"title":["Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems"],"prefix":"10.1007","volume":"62","author":[{"given":"Kazumasa","family":"Okumoto","sequence":"first","affiliation":[]},{"given":"Takuro","family":"Fukunaga","sequence":"additional","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,21]]},"reference":[{"key":"9483_CR1","series-title":"Cambridge London Mathematical Society Lecture Notes Series","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1017\/CBO9780511662089.005","volume-title":"Surveys in Combinatorics","author":"A. Frank","year":"1993","unstructured":"Frank, A.: Applications of submodular functions. In: Surveys in Combinatorics. Cambridge London Mathematical Society Lecture Notes Series, vol. 187, pp. 85\u2013136 (1993)"},{"key":"9483_CR2","volume-title":"Submodular Function and Optimization","author":"S. Fujishige","year":"1991","unstructured":"Fujishige, S.: Submodular Function and Optimization. North-Holland, Amsterdam (1991)"},{"key":"9483_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-642-13036-6_2","volume-title":"Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization","author":"T. Fukunaga","year":"2010","unstructured":"Fukunaga, T.: Computing minimum multiway cuts in hypergraphs from hypertree packings. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 6080, pp. 15\u201328. Springer, Berlin (2010)"},{"key":"9483_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N. Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50, 49\u201361 (2004)","journal-title":"J. Algorithms"},{"key":"9483_CR5","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1023\/A:1009833626004","volume":"3","author":"L. Gasieniec","year":"1999","unstructured":"Gasieniec, L., Jansson, J., Lingas, A., \u00d3stlin, A.: On the complexity of constructing evolutionary trees. J. Comb. Optim. 3, 183\u2013197 (1999)","journal-title":"J. Comb. Optim."},{"key":"9483_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":"9483_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.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19, 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"9483_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S. Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Math. Program. 112, 45\u201364 (2008)","journal-title":"Math. Program."},{"key":"9483_CR9","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1137\/050631616","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, 1329\u20131341 (2006)","journal-title":"SIAM J. Comput."},{"key":"9483_CR10","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":"9483_CR11","unstructured":"Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Internal Report B 96-02, Bericht FU Berlin Fachbereich Mathematik und Informatik (1995)"},{"key":"9483_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"E.L. Lawler","year":"1973","unstructured":"Lawler, E.L.: Cutsets and partitions of hypergraphs. Networks 3, 275\u2013285 (1973)","journal-title":"Networks"},{"key":"9483_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-9260(00)00008-0","volume":"30","author":"W.-K. Mak","year":"2000","unstructured":"Mak, W.-K., Wong, D.F.: A fast hypergraph min-cut algorithm for circuit partitioning. Integration 30, 1\u201311 (2000)","journal-title":"Integration"},{"key":"9483_CR14","first-page":"53","volume":"J86-D-1","author":"H. Nagamochi","year":"2003","unstructured":"Nagamochi, H.: Algorithms for the minimum partitioning problems in graphs. IEICE Trans. Inf. Syst. J86-D-1, 53\u201368 (2003)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"9483_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H. Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York (2008)"},{"key":"9483_CR16","volume-title":"Proceedings of AUSSOIS 1999","author":"M. Queyranne","year":"1999","unstructured":"Queyranne, M.: On optimum size-constrained set partitions. In: Proceedings of AUSSOIS 1999 (1999). http:\/\/www.iasi.cnr.it\/iasi\/aussois99\/queyranne.html"},{"key":"9483_CR17","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M. Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44, 585\u2013591 (1997)","journal-title":"J. ACM"},{"key":"9483_CR18","first-page":"159","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"M. Thorup","year":"2008","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\u2013166 (2008)"},{"key":"9483_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/3-540-55719-9_88","volume-title":"Proceedings of the 19th International Colloquium on Automata, Languages and Programming","author":"V.V. Vazirani","year":"1992","unstructured":"Vazirani, V.V., Yannakakis, M.: Suboptimal cuts: Their enumeration, weight and number. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 623, pp. 366\u2013377. Springer, Berlin (1992)"},{"key":"9483_CR20","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1016\/j.ipl.2010.05.003","volume":"110","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: Finding minimum 3-way cuts in hypergraphs. Inf. Process. Lett. 110, 554\u2013558 (2010)","journal-title":"Inf. Process. Lett."},{"key":"9483_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-540-92182-0_21","volume-title":"Proceedings of the 19th International Symposium on Algorithms and Computation","author":"M. Xiao","year":"2008","unstructured":"Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In: Proceedings of the 19th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 5369, pp. 208\u2013219. Springer, Berlin (2008)"},{"key":"9483_CR22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s10107-004-0510-2","volume":"102","author":"L. Zhao","year":"2005","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Math. Program. 102, 167\u2013183 (2005)","journal-title":"Math. Program."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9483-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9483-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9483-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T06:09:33Z","timestamp":1559887773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9483-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,21]]},"references-count":22,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9483"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9483-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,21]]}}}