{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T06:43:25Z","timestamp":1725950605136},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_189","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:21:27Z","timestamp":1330262487000},"page":"769-780","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the complexity of the maximum cut problem"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"63_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT 25 (1985) 2\u201323.","journal-title":"BIT"},{"key":"63_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(89)90221-4","volume":"31","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: Achromatic Number is NP-complete for cographs and interval graphs. Information Processing Letters 31 (1989) 135\u2013138.","journal-title":"Information Processing Letters"},{"key":"63_CR3","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the 25th Annual Symposium on Theory of Computing, pages 226\u2013234. ACM Press, 1993."},{"key":"63_CR4","volume-title":"Technical Report RUU-CS-92-12","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Technical Report RUU-CS-92-12, Department of Computer Science, Utrecht University, Utrecht, 1992. To appear in: Acta Cybernetica."},{"key":"63_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/TCAD.1987.1270247","volume":"6","author":"K. Chang","year":"1987","unstructured":"Chang, K., Du, D.: Efficient algorithms for the layer assignment problem. IEEE Trans. CAD 6 (1987) 67\u201378.","journal-title":"IEEE Trans. CAD"},{"key":"63_CR6","unstructured":"Chen, R., Kajitani, Y., Chan, S.: A graph theoretic via minimization algorithm for two layer printed circuit boards. IEEE Trans. Circuit Syst. (1983) 284\u2013299."},{"key":"63_CR7","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"4","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 4 (1985) 926\u2013934.","journal-title":"SIAM J. Comput."},{"key":"63_CR8","first-page":"311","volume-title":"Split graphs","author":"S. F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. In: Proceedings of the 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing, pages 311\u2013315. Louisiana State University, Baton Rouge, Louisiana, 1977."},{"key":"63_CR9","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"63_CR10","doi-asserted-by":"crossref","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 1 (1976) 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"63_CR11","first-page":"50","volume":"657","author":"K. Jansen","year":"1992","unstructured":"Jansen, K., Scheffler, P.: Some coloring results for tree like graphs. Workshop on Graph Theoretic Concepts in Computer Science. LNCS 657 (1992) 50\u201359.","journal-title":"LNCS"},{"key":"63_CR12","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D.S. Johnson","year":"1985","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 6 (1985) 434\u2013451.","journal-title":"J. Algorithms"},{"key":"63_CR13","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. in: Miller and Thatcher (eds.): Complexity of Computer Computations, Plenum Press (1972) 85\u2013104."},{"key":"63_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J.M. Muller","year":"1989","unstructured":"Muller, J.M., Spinrad, L.: Incremental modular decomposition. J. ACM. 36 (1989) 1\u201319.","journal-title":"J. ACM."},{"key":"63_CR15","unstructured":"Pinter, R.: Optimal layer assignment for interconnect. In: Proc. Int. Symp. Circuit Syst. (ISCAS) (1982) 398\u2013401."},{"key":"63_CR16","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7 (1986) 309\u2013322.","journal-title":"J. Algorithms"},{"key":"63_CR17","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/jgt.3190030302","volume":"3","author":"W.T. Trotter Jr.","year":"1979","unstructured":"Trotter, W.T.Jr., Harary, F.: On double and multiple interval graphs. J. Graph Theory 3 (1979) 205\u2013211.","journal-title":"J. Graph Theory"},{"key":"63_CR18","unstructured":"Wanke, E.: k-NLC graphs and polynomial algorithms. Bericht. Reihe Informatik 80. Universit\u00e4t Paderborn, 1991."},{"key":"63_CR19","unstructured":"Wimer, T.V.: Linear algorithms on k-terminal graphs. PhD thesis. Department of Computer Science. Clemson University, 1987."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:09:51Z","timestamp":1558267791000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_189","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}