{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T01:47:15Z","timestamp":1648777635686},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T00:00:00Z","timestamp":1538179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10878-018-0351-1","type":"journal-article","created":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T07:17:45Z","timestamp":1538205465000},"page":"1249-1265","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Balanced tree partition problems with virtual nodes"],"prefix":"10.1007","volume":"37","author":[{"given":"Baoling","family":"Ning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shouxu","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,29]]},"reference":[{"key":"351_CR1","doi-asserted-by":"crossref","unstructured":"Abitrboul S, Benjellourn O, Manolescu I, Milo T, Weber R (2002) Active XML: peer-to-peer data and web services integration. In: Proceedings of the 28th international conference on very large data bases, VLDB \u201902. VLDB Endowment, pp 1087\u20131090","DOI":"10.1016\/B978-155860869-6\/50115-3"},{"key":"351_CR2","doi-asserted-by":"crossref","unstructured":"Andreev K, R\u00e4cke H (2004) Balanced graph partitioning. In: Proceedings of the 16th annual ACM symposium on parallelism in algorithms and architectures, SPAA \u201904, New York, NY, USA. ACM, pp 120\u2013124","DOI":"10.1145\/1007912.1007931"},{"issue":"6","key":"351_CR3","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev K, Racke H (2006) Balanced graph partitioning. Theor. Comp. Syst. 39(6):929\u2013939","journal-title":"Theor. Comp. Syst."},{"key":"351_CR4","unstructured":"Arbenz P, Van\u00a0Lenthe G, Harry MU, M\u00fcller R, Sala M (2007) Multi-level mu-finite element analysis for human bone structures. In: Proceedings of the 8th international conference on applied parallel computing: state of the art in scientific computing, PARA\u201906. Springer, Berlin, pp 240\u2013250"},{"issue":"2","key":"351_CR5","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora S, Rao S, Vazirani U (2009) Expander flows, geometric embeddings and graph partitioning. J ACM 56(2):5:1\u20135:37","journal-title":"J ACM"},{"key":"351_CR6","doi-asserted-by":"crossref","unstructured":"Bansal N, Coppersmith D, Schieber B (2006) Minimizing setup and beam-on times in radiation therapy. In: Proceedings of the 9th international conference on approximation algorithms for combinatorial optimization problems, and 10th international conference on randomization and computation, APPROX\u201906\/RANDOM\u201906. Springer, Berlin, pp 27\u201338","DOI":"10.1007\/11830924_5"},{"key":"351_CR7","unstructured":"Bhatt SN, Leighton FT (1983) A framework for solving vlsi graph layout problems. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA"},{"issue":"2","key":"351_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"SN Bhatt","year":"1984","unstructured":"Bhatt SN, Leighton FT (1984) A framework for solving vlsi graph layout problems. J Comput Syst Sci 28(2):300\u2013343","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"351_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s10951-011-0225-1","volume":"15","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender HL, Schuurman P, Woeginger GJ (2012) Scheduling of pipelined operator graphs. J Sched 15(3):323\u2013332","journal-title":"J Sched"},{"issue":"2","key":"351_CR10","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.datak.2006.01.011","volume":"59","author":"A Bonifati","year":"2006","unstructured":"Bonifati A, Cuzzocrea A (2006) Storing and retrieving xpath fragments in structured p2p networks. Data Knowl Eng 59(2):247\u2013269","journal-title":"Data Knowl Eng"},{"key":"351_CR11","unstructured":"Bremer J-M, Gertz M (2003) On distributing XML repositories. In: International workshop on web and databases, San Diego, California, June 12\u201313, 2003, pp 73\u201378"},{"issue":"52","key":"351_CR12","doi-asserted-by":"publisher","first-page":"5415","DOI":"10.1016\/j.tcs.2009.05.013","volume":"410","author":"Z Cai","year":"2009","unstructured":"Cai Z, Chen Z-Z, Lin G (2009) A 3.4713-approximation algorithm for the capacitated multicast tree routing problem. Theor Comput Sci 410(52):5415\u20135424. \n                    https:\/\/doi.org\/10.1016\/j.tcs.2009.05.013","journal-title":"Theor Comput Sci"},{"key":"351_CR13","doi-asserted-by":"publisher","unstructured":"Cai Z, Chen Z-Z, Lin G, Wang L (2008) An improved approximation algorithm for the capacitated multicast tree routing problem. In: Proceedings of the 2nd international conference on combinatorial optimization and applications, COCOA, 2008. Springer, Berlin, pp 286\u2013295 \n                    https:\/\/doi.org\/10.1007\/978-3-540-85097-7_27","DOI":"10.1007\/978-3-540-85097-7_27"},{"key":"351_CR14","doi-asserted-by":"publisher","unstructured":"Cai Z, Goebel R, Lin G (2009) Size-constrained tree partitioning: a story on approximation algorithm design for the multicast k-tree routing problem. In: Proceedings of the 3rd international conference on combinatorial optimization and applications, COCOA \u201909. Springer, Berlin, pp 363\u2013374 \n                    https:\/\/doi.org\/10.1007\/978-3-642-02026-1_34","DOI":"10.1007\/978-3-642-02026-1_34"},{"issue":"3","key":"351_CR15","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2009.05.031","volume":"412","author":"Z Cai","year":"2011","unstructured":"Cai Z, Goebel R, Lin G (2011) Size-constrained tree partitioning: approximating the multicast k-tree routing problem. Theor Comput Sci 412(3):240\u2013245. \n                    https:\/\/doi.org\/10.1016\/j.tcs.2009.05.031","journal-title":"Theor Comput Sci"},{"key":"351_CR16","doi-asserted-by":"publisher","unstructured":"Cai Z, Lin G, Xue G (2005) Improved approximation algorithms for the capacitated multicast routing problem. In: Proceedings of the 11th annual international conference on computing and combinatorics, COCOON\u201905. Springer, Berlin, pp 136\u2013145. \n                    https:\/\/doi.org\/10.1007\/11533719_16","DOI":"10.1007\/11533719_16"},{"issue":"4","key":"351_CR17","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/2389241.2389251","volume":"37","author":"G Cong","year":"2012","unstructured":"Cong G, Fan W, Kementsietsidis A, Li J, Liu X (2012) Partial evaluation for distributed xpath query processing and beyond. ACM Trans Database Syst 37(4):32:1\u201332:43","journal-title":"ACM Trans Database Syst"},{"key":"351_CR18","doi-asserted-by":"crossref","unstructured":"Delling D, Goldberg AV, Pajor T, Werneck RF (2011) Customizable route planning. In: Proceedings of the 10th international conference on experimental algorithms, SEA\u201911. Springer, Berlin, pp 376\u2013387","DOI":"10.1007\/978-3-642-20662-7_32"},{"issue":"4","key":"351_CR19","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s002360050049","volume":"33","author":"J D\u00edaz","year":"1996","unstructured":"D\u00edaz J, Serna MJ, Tor\u00e1n J (1996) Parallel approximation schemes for problems on planar graphs. Acta Informatica 33(4):387\u2013408","journal-title":"Acta Informatica"},{"issue":"3","key":"351_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz J, Petit J, Serna M (2002) A survey of graph layout problems. ACM Comput Surv 34(3):313\u2013356","journal-title":"ACM Comput Surv"},{"key":"351_CR21","doi-asserted-by":"crossref","unstructured":"Feldmann AE (2012) Fast balanced partitioning is hard even on grids and trees. In: Proceedings of the 37th international conference on mathematical foundations of computer science, MFCS\u201912. Springer, Berlin, pp 372\u2013382","DOI":"10.1007\/978-3-642-32589-2_34"},{"issue":"2","key":"351_CR22","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00453-013-9802-3","volume":"71","author":"AE Feldmann","year":"2015","unstructured":"Feldmann AE, Foschini L (2015) Balanced partitions of trees and applications. Algorithmica 71(2):354\u2013376","journal-title":"Algorithmica"},{"key":"351_CR23","unstructured":"Feldmann Andreas E, Widmayer P (2011) An o(n4) time algorithm to compute the bisection width of solid grid graphs. In: Proceedings of the 19th European conference on algorithms, ESA\u201911. Springer, Berlin, pp 143\u2013154"},{"key":"351_CR24","unstructured":"Feldmann AE, Widmayer P (2011) Restricted cuts for bisections in solid grids: a proof via polygons. In: Proceedings of the 37th international conference on graph-theoretic concepts in computer science, WG\u201911. Springer, Berlin, pp 143\u2013154"},{"issue":"S1","key":"351_CR25","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1287\/opre.40.1.S170","volume":"40","author":"T Feo","year":"1992","unstructured":"Feo T, Goldschmidt O, Khellaf M (1992) One-half approximation algorithms for the k-partition problem. Oper Res 40(S1):170\u2013173","journal-title":"Oper Res"},{"issue":"2","key":"351_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/net.3230200205","volume":"20","author":"TA Feo","year":"1990","unstructured":"Feo TA, Khellaf M (1990) A class of bounded approximation algorithms for graph partitioning. Networks 20(2):181\u2013195","journal-title":"Networks"},{"key":"351_CR27","doi-asserted-by":"crossref","unstructured":"Jagadish HV, Lakshmanan Laks VS, Milo T, Srivastava D, Vista D (1999) Querying network directories. In: Proceedings of the 1999 ACM SIGMOD international conference on management of data, SIGMOD \u201999, New York, NY, USA. ACM, pp 133\u2013144","DOI":"10.1145\/304182.304194"},{"key":"351_CR28","unstructured":"Kirkpatrick DG, Hell P (1978) On the completeness of a generalized matching problem. In: Proceedings of the 10th annual ACM symposium on theory of computing, STOC \u201978, New York, NY, USA. ACM, pp 240\u2013245"},{"key":"351_CR29","doi-asserted-by":"crossref","unstructured":"Krauthgamer R, Naor J, Schwartz R (2009) Partitioning graphs into balanced components. In: roceedings of the 20h annual ACM-SIAM symposium on discrete algorithms, SODA \u201909, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp 942\u2013949","DOI":"10.1137\/1.9781611973068.102"},{"issue":"3","key":"351_CR30","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/882262.882264","volume":"22","author":"V Kwatra","year":"2003","unstructured":"Kwatra V, Sch\u00f6dl A, Essa I, Turk G, Bobick A (2003) Graphcut textures: image and video synthesis using graph cuts. ACM Trans Graph 22(3):277\u2013286","journal-title":"ACM Trans Graph"},{"issue":"3","key":"351_CR31","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton RJ, Tarjan RE (1980) Applications of a planar separator theorem. SIAM J Comput 9(3):615\u2013627","journal-title":"SIAM J Comput"},{"issue":"3","key":"351_CR32","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1147\/rd.183.0217","volume":"18","author":"JA Lukes","year":"1974","unstructured":"Lukes JA (1974) Efficient algorithm for the partitioning of trees. IBM J Res Dev 18(3):217\u2013224","journal-title":"IBM J Res Dev"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0351-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0351-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0351-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T23:58:43Z","timestamp":1569715123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0351-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,29]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["351"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0351-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,29]]},"assertion":[{"value":"29 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}