{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:39Z","timestamp":1725663279219},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540102915"},{"type":"electronic","value":"9783540384359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10291-4_11","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:09:04Z","timestamp":1330189744000},"page":"137-149","source":"Crossref","is-referenced-by-count":1,"title":["Graph grammars and the complexity gap in the isomorphism problem for acyclic digraphs"],"prefix":"10.1007","author":[{"given":"M.","family":"Schnitzler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"A. V. Aho","year":"1972","unstructured":"A.V. AHO \u2014 M.R. GAREY \u2014 J.D. ULLMAN, The Transitive Reduction of a Directed Graph, SIAM J. Comput. 1 (1972), 131\u2013137.","journal-title":"SIAM J. Comput."},{"key":"11_CR2","unstructured":"K.S. BOOTH \u2014 C.J. COLBOURN, Problems Polynomially Equivalent to Graph Isomorphism, Techn. Rep. CS-77-o4, Comput. Science Dept., Univ. of Waterloo, 1979."},{"key":"11_CR3","unstructured":"D.G. CORNEIL, Recent Results on the Graph Isomorphism Problem, Proc. 8th Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, 1978, pp. 13\u201331."},{"key":"11_CR4","volume-title":"Structural Models: An Introduction to the Theory of Directed Graphs","author":"F. Harary","year":"1965","unstructured":"F. HARARY \u2014 R.Z. NORMAN \u2014 D. CARTWRIGHT, \"Structural Models: An Introduction to the Theory of Directed Graphs\", John Wiley & Sons, New York\/London\/Sidney, 1965."},{"key":"11_CR5","first-page":"3","volume":"81","author":"E. L. Lawler","year":"1976","unstructured":"E.L. LAWLER, Graphical Algorithms and their Complexity, Mathematical Centre Tracts 81 (1976), 3\u201332, Amsterdam.","journal-title":"Mathematical Centre Tracts"},{"key":"11_CR6","unstructured":"M. NAGL, Formale Sprachen von markierten Graphen, Arbeitsber. d. Inst. f. Math. Masch. u. Datenver. 7 4, Erlangen, 1974."},{"key":"11_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-01443-0","volume-title":"Graph-Grammatiken: Theorie, Anwendungen, Implementierung","author":"M. Nagl","year":"1979","unstructured":"M. NAGL, \"Graph-Grammatiken: Theorie, Anwendungen, Implementierung\", Vieweg, Braunschweig, 1979."},{"key":"11_CR8","volume-title":"Graphentheorie mit Algorithmen und Anwendungen","author":"H. Noltemeier","year":"1976","unstructured":"H. NOLTEMEIER, \"Graphentheorie mit Algorithmen und Anwendungen\", W. de Gruyter, Berlin, 1976."},{"key":"11_CR9","unstructured":"M.SCHNITZLER, Graph Grammars for Acyclic Digraphs, Discussion Paper 8005, Lehrstuhl f\u00fcr Informatik III, RWTH Aachen, 1980."},{"key":"11_CR10","first-page":"65","volume-title":"Discrete Structures and Algorithms","author":"F. Sschweiggert","year":"1980","unstructured":"F. SSCHWEIGGERT, On the Relative Complexitiy in Deciding Graph Isomorphism, in \"Discrete Structures and Algorithms\" (U. Pape, ed.), Proceed. 5th Conf. on Graphtheoretic Concepts in Computer Science, Berlin (West), 1979, pp. 65\u201376, C. Hanser Verlag, M\u00fcnchen\/Wien, 1980."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"J. VALDES \u2014 R.E. TARJAN \u2014 E.L. LAWLER, The Recognition of Series Parallel Digraphs, Proc. 11th Ann. ACM Symp. on Theory of Computing, Atlanta, 1979, pp. 1\u201312.","DOI":"10.1145\/800135.804393"}],"container-title":["Lecture Notes in Computer Science","Graphtheoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10291-4_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:02:53Z","timestamp":1605643373000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10291-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540102915","9783540384359"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-10291-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}