{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T11:44:40Z","timestamp":1769082280050,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T00:00:00Z","timestamp":1585353600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T00:00:00Z","timestamp":1585353600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00453-020-00701-x","type":"journal-article","created":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T13:02:25Z","timestamp":1585400545000},"page":"2606-2643","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Tree Partitioning"],"prefix":"10.1007","volume":"82","author":[{"given":"Zhao","family":"An","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,28]]},"reference":[{"issue":"6","key":"701_CR1","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev, K., R\u00e4cke, H.: Balanced graph partitioning. Theory Comput. Syst. 39(6), 929\u2013939 (2006)","journal-title":"Theory Comput. Syst."},{"key":"701_CR2","doi-asserted-by":"crossref","unstructured":"Arbenz, P., van Lenthe, G., Mennel, U., M\u00fcller, R., Sala, M.: Multi-level $$\\mu$$-finite element analysis for human bone structures. In: Proceedings of the 8th International Workshop on Applied Parallel Computing, Volume 4699 of Lecture Notes in Computer Science, pp. 240\u2013250. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-75755-9_30"},{"issue":"2","key":"701_CR3","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S Bhatt","year":"1984","unstructured":"Bhatt, S., Leighton, F.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"701_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"H Bodlaender","year":"2015","unstructured":"Bodlaender, H., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"701_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"H Bodlaender","year":"2016","unstructured":"Bodlaender, H., Drange, P., Dregi, M., Fomin, F., Lokshtanov, D., Pilipczuk, M.: A $$c^k n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1\u20131","key":"701_CR6","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02170066","volume":"53","author":"\u00c1 Boscznay","year":"1989","unstructured":"Boscznay, \u00c1.: On the lower estimation of non-averaging sets. Acta Math. Hung. 53(1\u20131), 155\u2013157 (1989)","journal-title":"Acta Math. Hung."},{"issue":"6","key":"701_CR7","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.jcss.2006.11.001","volume":"73","author":"J Chen","year":"2007","unstructured":"Chen, J., Kanj, I., Perkovic, L., Sedgwick, E., Xia, G.: Genus characterizes the complexity of certain graph problems: some tight results. J. Comput. Syst. Sci. 73(6), 892\u2013907 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"701_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.tcs.2005.02.003","volume":"339","author":"Y Chen","year":"2005","unstructured":"Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339(2\u20133), 167\u2013199 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"701_CR9","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2009","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"701_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer, Berlin (2015)","edition":"1"},{"key":"701_CR11","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A., Pajor, T., Werneck, R.: Customizable route planning. In: Proceedings of the 10th International Symposium on Experimental Algorithms, Volume 6630 of Lecture Notes in Computer Science, pp. 376\u2013387. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-20662-7_32"},{"key":"701_CR12","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E Demaine","year":"2005","unstructured":"Demaine, E., Fomin, F., Hajiaghayi, M., Thilikos, D.: Subexponential parameterized algorithms on bounded-genus graphs and $$H$$-minor-free graphs. J. ACM 52, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"701_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, New York (2013)"},{"key":"701_CR14","unstructured":"Feldmann, A.: Balanced partitions of grids and related graphs. Ph.D. thesis, ETH, Zurich, Switzerland (2012)"},{"issue":"2","key":"701_CR15","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00453-013-9802-3","volume":"71","author":"A Feldmann","year":"2015","unstructured":"Feldmann, A., Foschini, L.: Balanced partitions of trees and applications. Algorithmica 71(2), 354\u2013376 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"701_CR16","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-014-9928-y","volume":"71","author":"A Feldmann","year":"2015","unstructured":"Feldmann, A., Widmayer, P.: An $$O(n^4)$$ time algorithm to compute the bisection width of solid grid graphs. Algorithmica 71(1), 181\u2013200 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"701_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"701_CR18","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2010","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2010)"},{"key":"701_CR19","unstructured":"Fomin, F., Kolay, S., Lokshtanov, D., Panolan, F., Saurabh, S.: Subexponential algorithms for rectilinear Steiner tree and arborescence problems. In: Proceedings of the 32nd International Symposium on Computational Geometry, Volume 51 of LIPIcs, pp. 39:1\u201339:15 (2016)"},{"key":"701_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"2","key":"701_CR21","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","volume":"17","author":"G Hardy","year":"1918","unstructured":"Hardy, G., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17(2), 75\u2013115 (1918)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"701_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"701_CR23","first-page":"280","volume":"34","author":"C Jones","year":"1996","unstructured":"Jones, C.: Generalized hockey stick identities and $$N$$-dimensional blockwalking. Fibonacci Q. 34(3), 280\u2013288 (1996)","journal-title":"Fibonacci Q."},{"key":"701_CR24","doi-asserted-by":"crossref","unstructured":"Klein, P., Marx, D.: A subexponential parameterized algorithm for subset TSP on planar graphs. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1812\u20131830 (2014)","DOI":"10.1137\/1.9781611973402.131"},{"key":"701_CR25","series-title":"Vol. 842 of Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Vol. 842 of Lecture Notes in Computer Science. Springer, Berlin (1994)"},{"key":"701_CR26","unstructured":"MacGregor, R.: On partitioning a graph: a theoretical and empirical study. Ph.D. thesis, University of California at Berkeley, California, USA (1978)"},{"key":"701_CR27","doi-asserted-by":"crossref","unstructured":"Madry, A.: Fast approximation algorithms for cut-based problems in undirected graphs. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science, pp. 245\u2013254 (2010)","DOI":"10.1109\/FOCS.2010.30"},{"key":"701_CR28","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"4","key":"701_CR29","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"701_CR30","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"701_CR31","unstructured":"R\u00e4cke, H., Stotz, R.: Improved approximation algorithms for balanced partitioning problems. In: Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, Volume 47 of LIPIcs, pp. 58:1\u201358:14 (2016)"},{"issue":"8","key":"701_CR32","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888\u2013905 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"701_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00224-014-9557-5","volume":"57","author":"R van Bevern","year":"2015","unstructured":"van Bevern, R., Feldmann, A., Sorge, M., Such\u00fd, O.: On the parameterized complexity of computing balanced partitions in graphs. Theory Comput. Syst. 57(1), 1\u201335 (2015)","journal-title":"Theory Comput. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00701-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00701-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00701-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,28]],"date-time":"2021-03-28T00:16:48Z","timestamp":1616890608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00701-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,28]]},"references-count":33,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["701"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00701-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,28]]},"assertion":[{"value":"8 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}