{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:17Z","timestamp":1740122417747,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100013904","name":"National Physical Science Consortium","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100013904","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00534-y","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T10:02:40Z","timestamp":1581069760000},"page":"1659-1679","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Isolation branching: a branch and bound algorithm for the k-terminal cut problem"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1176-5159","authenticated-orcid":false,"given":"Mark","family":"Velednitsky","sequence":"first","affiliation":[]},{"given":"Dorit S.","family":"Hochbaum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,7]]},"reference":[{"key":"534_CR1","doi-asserted-by":"crossref","unstructured":"Boykov Y, Veksler O, Zabih R (1998) Markov random fields with efficient approximations. In: 1998 Proceedings. 1998 IEEE computer society conference on Computer vision and pattern recognition. pp. 648\u2013655","DOI":"10.1109\/CVPR.1998.698673"},{"key":"534_CR2","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Naor JS, Schwartz R (2013) Simplex partitioning via exponential clocks and the multiway cut problem. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing. pp. 535\u2013544","DOI":"10.1145\/2488608.2488675"},{"key":"534_CR3","doi-asserted-by":"crossref","unstructured":"C\u0103linescu G, Karloff H, Rabani Y (1998) An improved approximation algorithm for multiway cut. In: Proceedings of the thirtieth annual ACM symposium on theory of computing. pp. 48\u201352","DOI":"10.1145\/276698.276711"},{"issue":"1","key":"534_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J Chen","year":"2009","unstructured":"Chen J, Liu Y, Lu S (2009) An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1):1\u201313","journal-title":"Algorithmica"},{"issue":"4","key":"534_CR5","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus E, Johnson DS, Papadimitriou CH, Seymour PD, Yannakakis M (1994) The complexity of multiterminal cuts. SIAM J Comput 23(4):864\u2013894","journal-title":"SIAM J Comput"},{"key":"534_CR6","doi-asserted-by":"crossref","unstructured":"Fern XZ, Brodley CE (2004) Solving cluster ensemble problems by bipartite graph partitioning. In: Proceedings of the twenty-first international conference on machine learning. p.\u00a036","DOI":"10.1145\/1015330.1015414"},{"key":"534_CR7","doi-asserted-by":"crossref","unstructured":"Goldberg AV, Tardos \u00c9, Tarjan RE (1989) Network flow algorithms. Technical report, Cornell University Operations Research and Industrial Engineering","DOI":"10.21236\/ADA214689"},{"issue":"1","key":"534_CR8","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt O, Hochbaum DS (1994) A polynomial algorithm for the k-cut problem for fixed k. Math Oper Res 19(1):24\u201337","journal-title":"Math Oper Res"},{"key":"534_CR9","unstructured":"Hagberg A, Swart P, S\u00a0Chult D (2008) Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States)"},{"key":"534_CR10","volume-title":"Approximation algorithms for NP-hard problems","author":"DS Hochbaum","year":"1996","unstructured":"Hochbaum DS (1996) Approximation algorithms for NP-hard problems. PWS Publishing Co, Gretna"},{"issue":"2","key":"534_CR11","doi-asserted-by":"publisher","first-page":"026107","DOI":"10.1103\/PhysRevE.65.026107","volume":"65","author":"P Holme","year":"2002","unstructured":"Holme P, Kim BJ (2002) Growing scale-free networks with tunable clustering. Phys Rev E 65(2):026107","journal-title":"Phys Rev E"},{"issue":"3","key":"534_CR12","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"DR Karger","year":"2004","unstructured":"Karger DR, Klein P, Stein C, Thorup M, Young NE (2004) Rounding algorithms for a geometric embedding of minimum multiway cut. Math Oper Res 29(3):436\u2013461","journal-title":"Math Oper Res"},{"issue":"1","key":"534_CR13","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359\u2013392","journal-title":"SIAM J Sci Comput"},{"key":"534_CR14","doi-asserted-by":"crossref","unstructured":"Manokaran R, Naor JS, Raghavendra P, Schwartz R (2008) Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. In: Proceedings of the fortieth annual ACM symposium on theory of computing. pp. 11\u201320","DOI":"10.1145\/1374376.1374379"},{"key":"534_CR15","doi-asserted-by":"crossref","unstructured":"Marx D (2004) Parameterized graph separation problems. In: International workshop on parameterized and exact computation. pp. 71\u201382. Springer","DOI":"10.1007\/978-3-540-28639-4_7"},{"key":"534_CR16","doi-asserted-by":"crossref","unstructured":"Sharma A, Vondr\u00e1k J (2014) Multiway cut, pairwise realizable distributions, and descending thresholds. In: Proceedings of the forty-sixth annual ACM symposium on theory of computing. pp. 724\u2013733","DOI":"10.1145\/2591796.2591866"},{"issue":"3","key":"534_CR17","first-page":"428","volume":"19","author":"M Stein","year":"2013","unstructured":"Stein M, Geyer-Schulz A (2013) A comparison of five programming languages in a graph clustering scenario. J Univers Comput Sci 19(3):428\u2013456","journal-title":"J Univers Comput Sci"},{"key":"534_CR18","doi-asserted-by":"crossref","unstructured":"Velednitsky M (2019) Solving $$(k-1)$$-stable instances of k-terminal cut with isolating cuts. In: International conference on combinatorial optimization and applications. springer","DOI":"10.1007\/978-3-030-36412-0_39"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00534-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00534-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00534-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:44:02Z","timestamp":1664354642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00534-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,7]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["534"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00534-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,7]]},"assertion":[{"value":"7 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}