{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T13:27:35Z","timestamp":1772458055243,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540507284","type":"print"},{"value":"9783540460763","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_32","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:32:03Z","timestamp":1330201923000},"page":"1-10","source":"Crossref","is-referenced-by-count":36,"title":["NC-algorithms for graphs with small treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","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 \u2014 A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277\u2013284, 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Problems easy for tree-decomposable graphs (extended abstract). In Proc. 15 th ICALP, pages 38\u201351, Springer Verlag, Lect. Notes in Comp. Sc. 317, 1988.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"1_CR4","volume-title":"Linear time algorithms for NP-hard problems on graphs embedded in k-trees","author":"S. Arnborg","year":"1984","unstructured":"S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems on graphs embedded in k-trees. TRITA-NA-8404, Dept. of Num. Anal. and Comp. Sci., Royal Institute of Technology, Stockholm, Sweden, 1984."},{"key":"1_CR5","series-title":"Technical Report","volume-title":"Classes of Graphs with Bounded Treewidth","author":"H. L. Bodlaender","year":"1986","unstructured":"H. L. Bodlaender. Classes of Graphs with Bounded Treewidth. Technical Report RUU-CS-86-22, Dept. Of Comp. Science, University of Utrecht, Utrecht, 1986."},{"key":"1_CR6","unstructured":"H. L. Bodlaender. Dynamic programming algorithms on graphs with bounded tree-width. Tech. Rep., Lab. for Comp. Science, M.I.T., 1987. Extended abstract in proceedings ICALP 88."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. Polynomial algorithms for Graph Isomorphism and Chromatic Index on partial k-trees. In Proc. 1st Scandinavian Workshop on Algorithm Theory, pages 223\u2013232, Springer Verlag LNCS 318, 1988.","DOI":"10.1007\/3-540-19487-8_26"},{"key":"1_CR8","unstructured":"N. Chandrasekharan and S. S. Iyengar. NC Algorithms for Recognizing Chordal Graphs and k-Trees. Tech. Rep. 86-020, Dept. of Comp. Science, Louisiana State University, 1986."},{"key":"1_CR9","unstructured":"B. Courcelle. Recognizability and Second-Order Definability for Sets of Finite Graphs. Preprint, Universite de Bordeaux, 1987."},{"key":"1_CR10","unstructured":"J. Engelfriet, G. Leih, and E. Welzl. Characterization and complexity of boundary graph languages. 1987. Manuscript."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston. On seach, decision and the efficiency of polynomial-time algorithms. 1988. Extended abstract.","DOI":"10.1145\/73007.73055"},{"key":"1_CR12","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(88)90080-4","volume":"27","author":"A. M. Gibbons","year":"1988","unstructured":"A. M. Gibbons, A. Israeli, and W. Rytter. Parallel o(log n) time edge-coloring of trees and halin graphs. Inform. Proc. Letters, 27:43\u201352, 1988.","journal-title":"Inform. Proc. Letters"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"G. Miller and J. Reif. Parallel tree contraction and its application. In Proc. of the 26th Annual IEEE Symp. on the Foundations of Comp. Science, pages 478\u2013489, 1985.","DOI":"10.1109\/SFCS.1985.43"},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. of Algorithms, 7:309\u2013322, 1986.","journal-title":"J. of Algorithms"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. Seymour. Graph minors. XIII. The disjoint paths problem. 1986. Manuscript.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"1_CR17","volume-title":"Linear-time algorithms for NP-complete problems restricted to partial k-trees. Report R-MATH-03\/87","author":"P. Scheffler","year":"1987","unstructured":"P. Scheffler. Linear-time algorithms for NP-complete problems restricted to partial k-trees. Report R-MATH-03\/87, Karl-Weierstrass-Institut F\u00fcr Mathematik, Berlin, GDR, 1987."},{"key":"1_CR18","unstructured":"P. Scheffler and D. Seese. A combinatorial and logical approach to linear-time computability. 1986. Extended abstract."}],"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\/3-540-50728-0_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T02:40:46Z","timestamp":1640918446000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989]]}}}