{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:42:47Z","timestamp":1725698567512},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_34","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"372-382","source":"Crossref","is-referenced-by-count":8,"title":["Fast Balanced Partitioning Is Hard Even on Grids and Trees"],"prefix":"10.1007","author":[{"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"34_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 of Computing Systems\u00a039(6), 929\u2013939 (2006)","journal-title":"Theory of Computing Systems"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Arbenz, P., van Lenthe, G., Mennel, U., M\u00fcller, R., Sala, M.: Multi-level \u03bc-finite element analysis for human bone structures. In: Proceedings of the 8th Workshop on State-of-the-art in Scientific and Parallel Computing (PARA), pp. 240\u2013250 (2007)","DOI":"10.1007\/978-3-540-75755-9_30"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"issue":"2","key":"34_CR4","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.T.: A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences\u00a028(2), 300\u2013343 (1984)","journal-title":"Journal of Computer and System Sciences"},{"issue":"68","key":"34_CR5","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.parco.2007.12.001","volume":"34","author":"C. Chevalier","year":"2008","unstructured":"Chevalier, C., Pellegrini, F.: PT-Scotch: A tool for efficient parallel graph ordering. Parallel Computing\u00a034(68), 318\u2013331 (2008)","journal-title":"Parallel Computing"},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A., Pajor, T., Werneck, R.: Customizable route planning. Experimental Algorithms, 376\u2013387 (2011)","DOI":"10.1007\/978-3-642-20662-7_32"},{"issue":"4","key":"34_CR7","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s002360050049","volume":"33","author":"J. D\u00edaz","year":"1996","unstructured":"D\u00edaz, J., Serna, M.J., Tor\u00e1n, J.: Parallel approximation schemes for problems on planar graphs. Acta Informatica\u00a033(4), 387\u2013408 (1996)","journal-title":"Acta Informatica"},{"issue":"1","key":"34_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/jctb.1998.1862","volume":"75","author":"R. Diestel","year":"1999","unstructured":"Diestel, R., Jensen, T.R., Gorbunov, K.Y., Thomassen, C.: Highly connected sets and the excluded grid theorem. Journal of Combinatorial Theory, Series B\u00a075(1), 61\u201373 (1999)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"34_CR9","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/jagm.1993.1013","volume":"14","author":"K. Diks","year":"1993","unstructured":"Diks, K., Djidjev, H.N., Sykora, O., Vrto, I.: Edge separators of planar and outerplanar graphs with applications. Journal of Algorithms\u00a014(2), 258\u2013279 (1993)","journal-title":"Journal of Algorithms"},{"key":"34_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198528678.001.0001","volume-title":"Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics","author":"H. Elman","year":"2005","unstructured":"Elman, H., Silvester, D., Wathen, A.: Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics. Oxford University Press, USA (2005)"},{"issue":"6","key":"34_CR11","doi-asserted-by":"publisher","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"28","author":"G. Even","year":"1999","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM Journal on Computing\u00a028(6), 2187\u20132214 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR12","unstructured":"Feldmann, A.E.: Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations. PhD thesis, ETH Zurich, Diss.-Nr. ETH: 20371 (April 2012)"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Feldmann, A.E., Das, S., Widmayer, P.: Restricted cuts for bisections in solid grids: A proof via polygons. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 143\u2013154 (2011)","DOI":"10.1007\/978-3-642-25870-1_14"},{"key":"34_CR14","unstructured":"Feldmann, A.E., Foschini, L.: Balanced partitions of trees and applications. In: 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 100\u2013111 (2012)"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Feldmann, A.E., Widmayer, P.: An O(n 4) time algorithm to compute the bisection width of solid grid graphs. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 143\u2013154 (2011)","DOI":"10.1007\/978-3-642-23719-5_13"},{"key":"34_CR16","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. (1979)"},{"issue":"3","key":"34_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science\u00a01(3), 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"key":"34_CR18","unstructured":"Karypis, G., Kumar, V.: METIS-unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report, University of Minnesota (1995)"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"Khot, S.A., Vishnoi, N.K.: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into \u21131. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Klein, P., Plotkin, S., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 682\u2013690 (1993)","DOI":"10.1145\/167088.167261"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Naor, J., Schwartz, R.: Partitioning graphs into balanced components. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 942\u2013949 (2009)","DOI":"10.1137\/1.9781611973068.102"},{"issue":"6","key":"34_CR22","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"34_CR23","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. Lipton","year":"1980","unstructured":"Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09, 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR24","unstructured":"MacGregor, R.M.: On Partitioning a Graph: a Theoretical and Empirical Study. PhD thesis, University of California, Berkeley (1978)"},{"key":"34_CR25","first-page":"97","volume":"29","author":"C. Papadimitriou","year":"1996","unstructured":"Papadimitriou, C., Sideri, M.: The bisection width of grid graphs. Theory of Computing Systems\u00a029, 97\u2013110 (1996)","journal-title":"Theory of Computing Systems"},{"key":"34_CR26","doi-asserted-by":"crossref","unstructured":"Park, J.K., Phillips, C.A.: Finding minimum-quotient cuts in planar graphs. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 766\u2013775 (1993)","DOI":"10.1145\/167088.167284"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) (2008)","DOI":"10.1145\/1374376.1374415"},{"issue":"5","key":"34_CR28","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S1064827593255135","volume":"18","author":"H.D. Simon","year":"1997","unstructured":"Simon, H.D., Teng, S.H.: How good is recursive bisection? SIAM Journal on Scientific Computing\u00a018(5), 1436\u20131445 (1997)","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"11","key":"34_CR29","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1109\/34.244673","volume":"15","author":"Z. Wu","year":"1993","unstructured":"Wu, Z., Leahy, R.: An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a015(11), 1101\u20131113 (1993)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,28]],"date-time":"2024-04-28T00:45:20Z","timestamp":1714265120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}