{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:53Z","timestamp":1725664493055},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_37","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:04:37Z","timestamp":1330272277000},"page":"453-464","source":"Crossref","is-referenced-by-count":5,"title":["Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"37_CR1","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 Journal of Algebraic and Discrete Methods 8 (1987), pp. 277\u2013284.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"S. ARNBORG, A. PROSKUROWSKI, and D. SEESE, Monadic second order logic, tree automata, and forbidden minors, Proceedings of the 4th Workshop on Computer Science Logic (CSL 90), pp. 1\u201316, Lecture Notes in Computer Science 533, Springer-Verlag, 1990.","DOI":"10.1007\/3-540-54487-9_49"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"H. L. BODLAENDER, A linear time algorithm for finding treedecompositions of small treewidth, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pp. 226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"H. L. BODLAENDER and T. HAGERUP, Parallel algorithms with optimal speedup for bounded treewidth, Proceedings of the 22nd International Colloquium on Automata, Languages, and Programming, 1995.","DOI":"10.1007\/3-540-60084-1_80"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"H. L. BODLAENDER and T. KLOKS, Better algorithms for the path-width and treewidth of graphs, Proceedings of the 18th International Colloquium on Automata, Languages, and Programming, pp. 544\u2013555, 1991.","DOI":"10.1007\/3-540-54233-7_162"},{"key":"37_CR6","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, \u201cComputers and Intractability: A Guide to the Theory of NP-completeness,\u201d Freeman, San Francisco, 1979."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"T. KLOKS, Treewidth \u2014 Computations and approximations, Springer-Verlag, Lecture Notes in Computer Science 842, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0304-3975(89)90011-X","volume":"63","author":"A. Lingas","year":"1989","unstructured":"A. LINGAS, Subgraph isomorphism for biconnected outerplanar graphs in cubic time, Theoretical Computer Science 63 (1989), pp. 295\u2013302.","journal-title":"Theoretical Computer Science"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"A. LINGAS and M. M. SYSLO, A polynomial-time algorithm for subgraph isomorphism of two-connected series parallel graphs, Proceedings of the 15th International Colloquium on Automata, Languages, and Programming pp. 394\u2013409, 1988.","DOI":"10.1007\/3-540-19488-6_130"},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. MATOU\u0160EK and R. THOMAS, On the complexity of finding iso-and other morphisms for partial k-trees, Discrete Mathematics 108 (1992), pp. 343\u2013364.","journal-title":"Discrete Mathematics"},{"key":"37_CR11","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D. Matula","year":"1978","unstructured":"D. MATULA, Subtree isomorphism in O(n5\/2), Annals of Discrete Mathematics 2 (1978), pp. 91\u2013106.","journal-title":"Annals of Discrete Mathematics"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0012-365X(84)90164-X","volume":"49","author":"A. Proskurowski","year":"1984","unstructured":"A. PROSKUROWSKI, Separating subgraphs in k-trees: cables and caterpillars, Discrete Mathematics 49 (1984), pp. 275\u2013285","journal-title":"Discrete Mathematics"},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0012-365X(74)90042-9","volume":"7","author":"D.J. Rose","year":"1974","unstructured":"D.J. ROSE, On simple characterization of k-trees, Discrete Mathematics 7 (1974), pp. 317\u2013322.","journal-title":"Discrete Mathematics"},{"key":"37_CR14","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. SEYMOUR, Graph Minors II. Algorithm aspects of tree-width, Journal of Algorithms 7 (1986), pp. 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M. M. Syslo","year":"1982","unstructured":"M. M. SYSLO, The subgraph isomorphism problem for outerplanar graphs, Theoretical Computer Science 17 (1982), pp. 91\u201397.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:02:35Z","timestamp":1605628955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}