{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:20:35Z","timestamp":1757452835069,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["1177114","11571252"],"award-info":[{"award-number":["1177114","11571252"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971139"],"award-info":[{"award-number":["11971139"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["201508330054","201908330090"],"award-info":[{"award-number":["201508330054","201908330090"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"The Grant in aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan","award":["18K11183"],"award-info":[{"award-number":["18K11183"]}]}],"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-00544-w","type":"journal-article","created":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T14:07:40Z","timestamp":1581948460000},"page":"1753-1773","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximation algorithms for the maximally balanced connected graph tripartition problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Guangting","family":"Chen","sequence":"first","affiliation":[]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Zhi-Zhong","family":"Chen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[]},{"given":"An","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,17]]},"reference":[{"key":"544_CR1","doi-asserted-by":"crossref","unstructured":"An Z, Feng Q, Kanj I, Xia G (2017) The complexity of tree partitioning. In: Proceedings of WADS 2017, pp 37\u201348","DOI":"10.1007\/978-3-319-62127-2_4"},{"key":"544_CR2","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1142\/S0218195903001190","volume":"13","author":"M Andersson","year":"2003","unstructured":"Andersson M, Gudmundsson J, Levcopoulos C, Narasimhan G (2003) Balanced partition of minimum spanning trees. Int J Comput Geometry Appl 13:303\u2013316","journal-title":"Int J Comput Geometry Appl"},{"key":"544_CR3","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/322290.322294","volume":"29","author":"RI Becker","year":"1982","unstructured":"Becker RI, Schach SR, Perl Y (1982) A shifting algorithm for min-max tree partitioning. JACM 29:58\u201367","journal-title":"JACM"},{"key":"544_CR4","unstructured":"Caraballo LE, Diaz-Banez JM, Kroher N (2018) A polynomial algorithm for balanced clustering via graph partitioning. arXiv:1801.03347"},{"key":"544_CR5","first-page":"177","volume":"9","author":"F Chataigner","year":"2007","unstructured":"Chataigner F, Salgado LRB, Wakabayashi Y (2007) Approximation and inapproximability results on balanced connected partitions of graphs. Discrete Math Theor Comput Sci 9:177\u2013192","journal-title":"Discrete Math Theor Comput Sci"},{"key":"544_CR6","doi-asserted-by":"crossref","unstructured":"Chen Y, Chen Z-Z, Lin G, Xu Y, Zhang A (2019) Approximation algorithms for maximally balanced connected graph partition. In: Proceedings of the 13th annual international conference on combinatorial optimization and applications (COCOA 2019), LNCS 11949, pp 130\u2013141","DOI":"10.1007\/978-3-030-36412-0_11"},{"key":"544_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0020-0190(96)00175-5","volume":"60","author":"J Chleb\u00edkov\u00e1","year":"1996","unstructured":"Chleb\u00edkov\u00e1 J (1996) Approximating the maximally balanced connected partition problem in graphs. Inf Process Lett 60:225\u2013230","journal-title":"Inf Process Lett"},{"key":"544_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0166-218X(03)00340-8","volume":"134","author":"R Cordone","year":"2004","unstructured":"Cordone R, Maffioli F (2004) On the complexity of graph tree partition problems. Discrete Appl Math 134:51\u201365","journal-title":"Discrete Appl Math"},{"key":"544_CR9","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(85)90008-3","volume":"10","author":"ME Dyer","year":"1985","unstructured":"Dyer ME, Frieze AM (1985) On the complexity of partitioning graphs into connected subgraphs. Discrete Appl Math 10:139\u2013153","journal-title":"Discrete Appl Math"},{"key":"544_CR10","doi-asserted-by":"crossref","first-page":"168","DOI":"10.5465\/ambpp.1991.4976828","volume":"1991","author":"GN Frederickson","year":"1991","unstructured":"Frederickson GN (1991) Optimal algorithms for tree partitioning. Proc SODA 1991:168\u2013177","journal-title":"Proc SODA"},{"key":"544_CR11","unstructured":"Frederickson GN, Zhou S (2017) Optimal parametric search for path and tree partitioning. arXiv:1711.00599"},{"key":"544_CR12","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"key":"544_CR13","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/jagm.1996.0848","volume":"24","author":"N Guttmann-Beck","year":"1997","unstructured":"Guttmann-Beck N, Hassin R (1997) Approximation algorithms for min\u2013max tree partition. J Algorithms 24:266\u2013286","journal-title":"J Algorithms"},{"key":"544_CR14","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0166-218X(98)00052-3","volume":"87","author":"N Guttmann-Beck","year":"1998","unstructured":"Guttmann-Beck N, Hassin R (1998) Approximation algorithms for minimum tree partition. Discrete Appl Math 87:117\u2013137","journal-title":"Discrete Appl Math"},{"key":"544_CR15","unstructured":"Gy\u00f6ri E (1976) On division of graphs to connected subgraphs, volume\u00a018 of Colloquia Mathematica Societatis Janos Bolyai, pages 485\u2013494"},{"key":"544_CR16","unstructured":"Kanj I, Komusiewicz C, Sorge M, van Leeuwen EJ (2018) Solving partition problems almost always requires pushing many vertices around. In: Proceedings of ESA 2018, LIPIcs 112, pp 51:1\u201351:14"},{"key":"544_CR17","unstructured":"Lesnick M, Wright M (2015) Interactive visualization of 2-D persistence modules. arxiv:1512.00180"},{"key":"544_CR18","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01896190","volume":"30","author":"L Lov\u00e1sz","year":"1977","unstructured":"Lov\u00e1sz L (1977) A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae 30:241\u2013251","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"544_CR19","unstructured":"Madkour AR, Nadolny P, Wright M (2017) Finding minimal spanning forests in a graph. arXiv:1705.00774"},{"key":"544_CR20","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/322234.322236","volume":"28","author":"Y Perl","year":"1981","unstructured":"Perl Y, Schach SR (1981) Max-min tree partitioning. JACM 28:5\u201315","journal-title":"JACM"},{"key":"544_CR21","doi-asserted-by":"crossref","unstructured":"Vaishali S, Atulya MS, Purohit N (2018) Efficient algorithms for a graph partitioning problem. In: Proceedings of FAW 2018, LNCS 10823, pp 29\u201342","DOI":"10.1007\/978-3-319-78455-7_3"},{"key":"544_CR22","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1007\/s10898-012-0028-8","volume":"57","author":"L Wang","year":"2013","unstructured":"Wang L, Zhang Z, Wu D, Wu W, Fan L (2013) Max-min weight balanced connected partition. J Global Optim 57:1263\u20131275","journal-title":"J Global Optim"},{"key":"544_CR23","doi-asserted-by":"crossref","unstructured":"Wu BY (2011) A 7\/6-approximation algorithm for the max-min connected bipartition problem on grid graphs. In: Proceedings of CGGA 2011, LNCS 7033, pp 188\u2013194","DOI":"10.1007\/978-3-642-24983-9_19"},{"key":"544_CR24","doi-asserted-by":"publisher","first-page":"1250005","DOI":"10.1142\/S179383091250005X","volume":"4","author":"BY Wu","year":"2013","unstructured":"Wu BY (2013) Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs. Discrete Math Algorithms Appl 4:1250005","journal-title":"Discrete Math Algorithms Appl"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00544-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00544-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00544-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:46:38Z","timestamp":1664354798000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00544-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,17]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["544"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00544-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,17]]},"assertion":[{"value":"17 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}