{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:28Z","timestamp":1725663628845},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194873"},{"type":"electronic","value":"9783540392880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19487-8_26","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:11:49Z","timestamp":1330182709000},"page":"223-232","source":"Crossref","is-referenced-by-count":10,"title":["Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"26_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":"26_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. 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":"26_CR3","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Which problems are easy for tree-decomposable graphs. 1987. Ext. abstract to appear in proc. ICALP 88.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski. Characterization and recognition of partial 3-trees. Siam J. Alg. Disc. Meth., 7:305\u2013314, 1986.","journal-title":"Siam J. Alg. Disc. Meth."},{"key":"26_CR5","series-title":"Tech. Rep.","volume-title":"Classes of Graphs with Bounded Treewidth","author":"H. L. Bodlaender","year":"1986","unstructured":"H. L. Bodlaender. Classes of Graphs with Bounded Treewidth. Tech. Rep. RUU-CS-86-22, Dept. Of Comp. Science, University of Utrecht, Utrecht, 1986."},{"key":"26_CR6","unstructured":"H. L. Bodlaender. Dynamic programming algorithms on graphs with bounded tree-width. Tech. Rep. MIT\/LCS\/TR-394, Lab. for Comp. Science, M.I.T., 1987. Ext. abstract to appear in proc. ICALP 88."},{"key":"26_CR7","series-title":"Tech. Rep.","volume-title":"NC-algorithms for graphs with small treewidth","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender. NC-algorithms for graphs with small treewidth. Tech. Rep. RUU-CS-88-4, Dept. of Comp. Science, Univ. of Utrecht, Utrecht, 1988."},{"key":"26_CR8","unstructured":"B. Courcelle. Recognizability and Second-Order Definability for Sets of Finite Graphs. Preprint, Universite de Bordeaux, Jan. 1987."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. 1987. To appear in JACM.","DOI":"10.1145\/44483.44491"},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer. The NP-completeness of edge-coloring. SIAM J. Comput, 10:718\u2013720, 1981.","journal-title":"SIAM J. Comput"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"J. E. Hopcroft and R. M. Karp. An n 5\/2 algorithm for maximum matching in bipartite graphs. SAIM J. on Comput., 225\u2013231, 1975.","DOI":"10.1137\/0202019"},{"key":"26_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":"D. S. Johnson. The NP-completeness column: an ongoing guide. J. of Algorithms, 6:434\u2013451, 1985.","journal-title":"J. of Algorithms"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. Seymour. Graph minors. III. Planar tree-width. J. Combin. Theory Series B, 36:49\u201364, 1984.","journal-title":"J. Combin. Theory Series B"},{"key":"26_CR14","unstructured":"N. Robertson and P. Seymour. Graph minors. X. Obstructions to tree-decompositions. 1986. Manuscript."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. Seymour. Graph minors. XII. Excluding a non-planar graph. 1986. Manuscript.","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"26_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":"26_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":"26_CR18","first-page":"342","volume-title":"Proc. WG'83 International Workshop on Graph Theoretic Concepts in Computer Science","author":"M. M. Sys\u0142o","year":"1983","unstructured":"M. M. Sys\u0142o. NP-complete problems on some tree-structured graphs: a review. In M. Nagl and J. Perl, editors, Proc. WG'83 International Workshop on Graph Theoretic Concepts in Computer Science, pages 342\u2013353, Univ. Verlag Rudolf Trauner, Linz, West Germany, 1983."},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, R. Tarjan, and E. L. Lawler. The recognition of series parallel digraphs. SIAM J. Comput., 11:298\u2013313, 1982.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SWAT 88"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19487-8_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:17:19Z","timestamp":1605626239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19487-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194873","9783540392880"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-19487-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}