{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:46:09Z","timestamp":1754109969220},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450426"},{"type":"electronic","value":"9783642450433"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45043-3_8","type":"book-chapter","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T14:05:50Z","timestamp":1384265150000},"page":"76-87","source":"Crossref","is-referenced-by-count":4,"title":["On the Parameterized Complexity of Computing Graph Bisections"],"prefix":"10.1007","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"8_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":"8_CR2","unstructured":"Arbenz, P.: Personal communication, ETH Z\u00fcrich (2013)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-540-75755-9_30","volume-title":"Applied Parallel Computing. State of the Art in Scientific Computing","author":"P. Arbenz","year":"2007","unstructured":"P.\u00a0Arbenz, G.\u00a0van Lenthe, U.\u00a0Mennel, R.\u00a0M\u00fcller, and M.\u00a0Sala. Multi-level \u03bc-finite element analysis for human bone structures. In Proc. 8th PARA, volume 4699 of LNCS, pages 240\u2013250. Springer, 2007."},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci.\u00a028(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Science\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theor. Comput. Science"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"key":"8_CR7","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proc. 28th STACS. LIPIcs, vol.\u00a09, pp. 165\u2013176. Dagstuhl (2011)"},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0221016","volume":"21","author":"T.N. Bui","year":"1992","unstructured":"Bui, T.N., Peck, A.: Partitioning planar graphs. SIAM J. Comput.\u00a021(2), 203\u2013215 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T.N. Bui","year":"1987","unstructured":"Bui, T.N., Chaudhuri, S., Leighton, F.T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica\u00a07(2), 171\u2013191 (1987)","journal-title":"Combinatorica"},{"issue":"40-42","key":"8_CR10","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci.\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"8_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-20662-7_32","volume-title":"Experimental Algorithms","author":"D. Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 376\u2013387. Springer, Heidelberg (2011)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W. Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2013.03.014","volume":"485","author":"A.E. Feldmann","year":"2013","unstructured":"Feldmann, A.E.: Fast balanced partitioning is hard, even on grids and trees. Theor. Comput. Sci.\u00a0485, 61\u201368 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR16","unstructured":"Feldmann, A.E., Foschini, L.: Balanced partitions of trees and applications. In: Proc. 29th STACS. LIPIcs, vol.\u00a014, pp. 100\u2013111. Dagstuhl (2012)"},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-642-23719-5_13","volume-title":"Algorithms \u2013 ESA 2011","author":"A.E. Feldmann","year":"2011","unstructured":"Feldmann, A.E., Widmayer, P.: An \n                  \n                    \n                  \n                  $\\mathcal{O}(n^4)$\n                 time algorithm to compute the bisection width of solid grid graphs. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 143\u2013154. Springer, Heidelberg (2011)"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \n                  \n                    \n                  \n                  $\\mathcal{F}$\n                -deletion: Approximation, kernelization and optimal fpt algorithms. In: Proc. 53rd FOCS, pp. 470\u2013479. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"8_CR19","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":"8_CR20","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.J.: Some simplified NP-complete graph problems. Theor. Comput. Science\u00a01(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Science"},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"issue":"3","key":"8_CR22","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J.\u00a051(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"key":"8_CR23","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: Proc. 46th FOCS, pp. 53\u201362. IEEE Computer Society (2005)","DOI":"10.1145\/2629614"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"issue":"3","key":"8_CR25","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.: Graphcut textures: Image and video synthesis using graph cuts. ACM T. Graphic.\u00a022(3), 277\u2013286 (2003)","journal-title":"ACM T. Graphic."},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"8_CR27","unstructured":"MacGregor, R.M.: On Partitioning a Graph: a Theoretical and Empirical Study. PhD thesis, University of California, Berkeley (1978)"},{"issue":"3","key":"8_CR28","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR29","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Treewidth reduction for constrained separation and bipartization problems. In: Proc. 27th STACS. LIPIcs, vol.\u00a05, pp. 561\u2013572. Dagstuhl (2010)"},{"key":"8_CR30","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. CoRR, abs\/1110.4765 (2011)"},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. ACM T. Algorithms 5 (1) (2008)","DOI":"10.1145\/1435375.1435385"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proc. 40th STOC, pp. 255\u2013264. ACM (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"8_CR33","unstructured":"Soumyanath, K., Deogun, J.S.: On the bisection width of partial k-trees. In: Proc. 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol.\u00a074, pp. 25\u201337 (1990)"},{"key":"8_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/BFb0029652","volume-title":"Mathematical Foundations of Computer Science 1990","author":"M. Wiegers","year":"1990","unstructured":"Wiegers, M.: The k-section of treewidth restricted graphs. In: Rovan, B. (ed.) MFCS 1990. LNCS, vol.\u00a0452, pp. 530\u2013537. Springer, Heidelberg (1990)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45043-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T06:11:00Z","timestamp":1558678260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45043-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450426","9783642450433"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45043-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}