{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:38Z","timestamp":1759639058015},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540416951"},{"type":"electronic","value":"9783540446934"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44693-1_32","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T05:10:18Z","timestamp":1181625018000},"page":"365-375","source":"Crossref","is-referenced-by-count":7,"title":["Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinsk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eike","family":"Seide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,3,16]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey, BIT, 25 (1985), pp. 2\u201323.","journal-title":"BIT"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems, Proceedings 27th ACM Symposium on the Theory of Computing, pp. 284\u2013293, 1995.","DOI":"10.1145\/225058.225140"},{"key":"32_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Proceedings of the Conference of Integer Programming and Combinatorial Optimization 99","author":"A.A. Ageev","year":"1999","unstructured":"A.A. Ageev and M.I. Sviridenko. Approximation algorithms for Maximum Cover-age and Max Cut with cardinality constraints. Proceedings of the Conference of Integer Programming and Combinatorial Optimization 99, LNCS 1610, pp. 17\u201330, 1999."},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Proceedings of the 24th IEEE Foundation of Computer Science, 1983, pp. 265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"key":"32_CR5","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"H.L. Bodlaender, A tourist guide through treewidth. Acta Cybernetica, 11 (1993), pp.1\u201323.","journal-title":"Acta Cybernetica"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (1996), pp.1305\u20131317.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR7","unstructured":"H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth. Avail-able at http:\/\/www.cs.ruu.nl\/~hansb\/index.html ."},{"key":"32_CR8","unstructured":"H.L. Bodlaender, Personal communication, August, 2000."},{"key":"32_CR9","first-page":"14","volume":"7","author":"H.L. Bodlaender","year":"2000","unstructured":"H.L. Bodlaender and K. Jansen. On the complexity of the Maximum Cut problem. Nordic Journal of Computing, 7(2000), pp. 14\u201331, 2000.","journal-title":"Nordic Journal of Computing"},{"key":"32_CR10","unstructured":"U. Feige, M. Karpinski and M. Langberg. A Note on Approximating MAX-BISECTION on Regular Graphs. ECCC( http:\/\/www.eccc.uni-trier.de\/eccc\/ ), TR00-043 (2000)."},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"U. Feige and R. Krauthgamer. A polylogarithmic approximation of the minimum bisection. To appear in Proceedings of the Foundation of Computer Science 2000.","DOI":"10.1109\/SFCS.2000.892070"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18, pp. 67\u201381, 1997.","DOI":"10.1007\/BF02523688"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson. Improved approximation algorithms for max-imum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42, pp. 1115\u20131145, 1995.","journal-title":"Journal of ACM"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing 4(1975), pp. 221\u2013225.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1007\/3-540-57960-5","volume-title":"Proceedings 2nd Annual European Symposium on Algorithms, (ESA)","author":"H.B. Hunt","year":"1994","unstructured":"H.B. Hunt, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.S. Rosenkrantz, R.E. Stearns. NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs. Proceedings 2nd Annual European Symposium on Algorithms, (ESA), LNCS 855, pp. 468\u2013477, Springer Verlag, June, 1994"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"E. Halperin and U. Zwick, Improved approximation algorithms for maximum graph bisection problems, Manuscript, 2000.","DOI":"10.1007\/3-540-45535-3_17"},{"key":"32_CR17","unstructured":"M. Jerrum, Personal communication, August, 2000."},{"key":"32_CR18","unstructured":"M. Karpinski, M. Kowaluk and A. Lingas. Approximation Algorithms for Max-Bisection on Low Degree Regular Graphs and Planar Graphs. ECCC http:\/\/www.eccc.uni-trier.de\/eccc\/ , TR00-051 (2000)."},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"S. Khanna and R. Motwani. Towards a Syntactic Characterization of PTAS. Proceedings of the 28th ACM Symposium on the Theory of Computing, 1996, pp. 329\u2013337.","DOI":"10.1145\/237814.237979"},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics, 36 (1979), pp. 177\u2013189.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 7 (1986), pp. 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"32_CR22","unstructured":"Y. Ye, A O.699-approximation algorithm for Max-Bisection, Submitted to Math-ematical Programming, available at http:\/\/dollar.biz.uiowa.edu\/col\/ye , 1999"}],"container-title":["Lecture Notes in Computer Science","STACS 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44693-1_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:29:51Z","timestamp":1556501391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44693-1_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540416951","9783540446934"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44693-1_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}