{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T18:40:33Z","timestamp":1736016033501,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":12,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540123105"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0000119","type":"book-chapter","created":{"date-parts":[[2005,10,5]],"date-time":"2005-10-05T10:17:45Z","timestamp":1128507465000},"page":"369-379","source":"Crossref","is-referenced-by-count":2,"title":["The isomorphism problem is polynomially solvable for certain graph languages"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Schnitzler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"K.S. BOOTH-C.J. COLBOURN, Problems Polynomially Equivalent to Graph Isomorphism, Techn. Rep. CS-77-04, Comp. Sci. Dep., Univ. Waterloo, 1979."},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"C.J. COLBOURN, The Complexity of Graph Isomorphism and Related Problems, Techn. Rep. 142\/80 (Ph.D. Thesis), Dep. Comp. Sci., Univ. Toronto, 1980.","DOI":"10.1016\/S0167-5060(08)70859-8"},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(78)90528-4","volume":"37","author":"P. Vigna Della","year":"1978","unstructured":"P. DELLA VIGNA-C. GHEZZI, Context-Free Graph Grammars, Information and Control 37 (1978), 207\u2013233.","journal-title":"Information and Control"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"J.E. HOPCROFT-J.K. WONG, Linear Time Algorithm for Isomorphism of Planar Graphs, Proc. 6th ACM Symp. on Theory of Computing, Seattle (WA), 1974, 172\u2013184.","DOI":"10.1145\/800119.803896"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0196-6774(81)90037-7","volume":"2","author":"D.S. Johnson","year":"1981","unstructured":"D.S. JOHNSON, The NP-Completeness Column: An Ongoing Guide, Journal of Algorithms 2 (1981), 393\u2013405.","journal-title":"Journal of Algorithms"},{"key":"25_CR6","unstructured":"M. KAUL, Linear Parsing of Graphs, this volume."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"E.M. LUKS, Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time, to appear in J. Comp. Syst. Sci.; short version in 21st IEEE Symp. Found. Comp. Sci., 1980, 42\u201349.","DOI":"10.1109\/SFCS.1980.24"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"M. NAGL, A Tutorial and Bibliographical Survey on Graph Grammars, in \u201cGraph-Grammars and Their Application to Computer Science and Biology\u201d (V. Claus-H. Ehrig-G. Rozenberg, eds.), Lect. Notes Comp. Sci. 73 (1979), 70\u2013126.","DOI":"10.1007\/BFb0025715"},{"key":"25_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-01443-0","volume-title":"Graph-Grammatiken: Theorie, Implementierung, Anwendungen","author":"M. Nagl","year":"1979","unstructured":"M. NAGL, \u201cGraph-Grammatiken: Theorie, Implementierung, Anwendungen\u201d, Friedr. Vieweg & Sohn, Braunschweig, 1979."},{"key":"25_CR10","volume-title":"Discussion Paper 8005","author":"M. Schnitzler","year":"1980","unstructured":"M. SCHNITZLER, Graph Grammars for Acyclic Digraphs, Discussion Paper 8005, Lehrstuhl Informatik III, RWTH Aachen, 1980."},{"key":"25_CR11","volume-title":"Dissertation","author":"M. Schnitzler","year":"1982","unstructured":"M. SCHNITZLER, Untersuchungen zur Komplexit\u00e4t des Graphenisomorphie-Problems mit Hilfe von Graph-Grammatiken, Dissertation, RWTH Aachen, 1982."},{"key":"25_CR12","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. VALDES-R.E. TARJAN-E.L. LAWLER, The Recognition of Series Parallel Digraphs, SIAM Journal on Computing 11 (1982), 298\u2013313.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Grammars and Their Application to Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0000119.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T18:12:34Z","timestamp":1736014354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0000119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540123105"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0000119","relation":{},"subject":[]}}