{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T09:19:47Z","timestamp":1778577587199,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,8]],"date-time":"2009-05-08T00:00:00Z","timestamp":1241740800000},"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":[[2011,4]]},"DOI":"10.1007\/s00453-009-9316-1","type":"journal-article","created":{"date-parts":[[2009,5,7]],"date-time":"2009-05-07T17:46:30Z","timestamp":1241718390000},"page":"510-520","source":"Crossref","is-referenced-by-count":6,"title":["Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem"],"prefix":"10.1007","volume":"59","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leizhen","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew Chi-Chih","family":"Yao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,5,8]]},"reference":[{"issue":"1","key":"9316_CR1","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.: A polynomial algorithm for the k-cut problem for fixed\u00a0k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"9316_CR2","first-page":"159","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908)","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 (STOC\u201908), pp. 159\u2013165. ACM, Victoria (2008)"},{"issue":"4","key":"9316_CR3","first-page":"601","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J.\u00a0ACM 43(4), 601\u2013640 (1996)","journal-title":"J.\u00a0ACM"},{"key":"9316_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S1571-0661(04)81002-8","volume":"78","author":"R.G. Downey","year":"2003","unstructured":"Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci. 78, 1\u201314 (2003)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"9316_CR5","first-page":"165","volume-title":"Proceedings of the 3rd Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201992)","author":"J. Hao","year":"1992","unstructured":"Hao, J., Orlin, J.B.: A faster algorithm for finding the minimum cut in a graph. In: Proceedings of the 3rd Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201992), pp. 165\u2013174. Society for Industrial and Applied Mathematics, Philadelphia (1992)"},{"issue":"1","key":"9316_CR6","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5(1), 54\u201366 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"9316_CR7","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(5), 225\u2013227 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9316_CR8","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(3), 507\u2013520 (2000)","journal-title":"Math. Program."},{"key":"9316_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/3-540-48686-0_16","volume-title":"Computing and Combinatorics Conference (COCOON\u201999)","author":"H. Nagamochi","year":"1999","unstructured":"Nagamochi, H., Katayama, S., Ibaraki, T.: A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. In: Computing and Combinatorics Conference (COCOON\u201999). LNCS, vol.\u00a01627, pp. 164\u2013173. Springer, Berlin (1999)"},{"key":"9316_CR10","first-page":"735","volume-title":"Proceedings of the 11th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"M.S. Levine","year":"2000","unstructured":"Levine, M.S.: Fast randomized algorithms for computing minimum {3,4,5,6}-way cuts. In: Proceedings of the 11th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201900), pp. 735\u2013742. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"issue":"1","key":"9316_CR11","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H. Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"9316_CR12","first-page":"26","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"J. Naor","year":"2001","unstructured":"Naor, J., Rabani, Y.: Tree packing and approximating k-cuts. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901), pp. 26\u201327. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"9316_CR13","first-page":"621","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"R. Ravi","year":"2002","unstructured":"Ravi, R., Sinha, A.: Approximating k-cuts via network strength. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902), pp. 621\u2013622. Society for Industrial and Applied Mathematics, Philadelphia (2002)"},{"key":"9316_CR14","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/3-540-61310-2_11","volume-title":"Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization","author":"S. Kapoor","year":"1996","unstructured":"Kapoor, S.: On minimum 3-cuts and approximating k-cuts using cut trees. In: Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 132\u2013146. Springer, London (1996)"},{"issue":"4","key":"9316_CR15","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.\u00a0Comb. Optim. 5(4), 397\u2013410 (2001)","journal-title":"J.\u00a0Comb. Optim."},{"issue":"1","key":"9316_CR16","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(1), 167\u2013183 (2005)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"9316_CR17","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.dam.2003.10.007","volume":"143","author":"L. Zhao","year":"2004","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: On generalized greedy splitting algorithms for multiway partition problems. Discrete Appl. Math. 143(1\u20133), 130\u2013143 (2004)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9316-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9316-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9316-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:04Z","timestamp":1559137504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9316-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9316"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9316-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,8]]}}}