{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T21:43:52Z","timestamp":1773265432016,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540194880","type":"print"},{"value":"9783540392910","type":"electronic"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_129","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:13:47Z","timestamp":1330200827000},"page":"379-393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Efficient analysis of graph properties on context-free graph languages"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Lengauer","sequence":"first","affiliation":[]},{"given":"Egon","family":"Wanke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"A. Arnborg, J. Lagergren, D. Seese, \u201dWhich problems are easy for tree-decomposable graphs?\u201d to appear in Proceedings of ICALP '88, Springer Lecture Notes in Computer Science (1988)","DOI":"10.1007\/3-540-19488-6_105"},{"key":"27_CR2","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M.W. Bern","year":"1987","unstructured":"M.W. Bern, E.L. Lawler, A.L. Wong, \u201dLinear-time computation of optimal subgraphs of decomposable graphs,\u201d Journal of Algorithms Vol. 8, pp. 216\u2013235 (1987)","journal-title":"Journal of Algorithms"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"F.J. Brandenburg, \u201dOn polynomial time graph grammars,\u201d Proceedings of STACS '88 (R. Cori, M.Wirsing, eds.), Springer Lecture Notes in Computer Science No. 294, pp. 227\u2013236 (1988)","DOI":"10.1007\/BFb0035847"},{"key":"27_CR4","unstructured":"B. Courcelle, Recognizability and monadic second order definability for sets of finite graphs, Research report 8634 Bordeaux I University (1986). Submitted for publication."},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"B. Courcelle, \u201dOn context-free sets of graphs and their monadic second order theory,\u201d Graph-Grammars and Their Application to Computer Science (H. Ehrig, A. Rosenfeld, G. Rozenberg, eds.), Springer Lecture Notes in Computer Science No. 291, pp. 133\u2013146 (1987)","DOI":"10.1007\/3-540-18771-5_50"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"B. Courcelle, \u201dAn axiomatic definition of context-free rewriting and its application to NLC graph grammars,\u201d Proceedings of STACS '88 (R. Cori, M.Wirsing, eds.), Springer Lecture Notes in Computer Science No. 294, pp. 237\u2013247 (1988)","DOI":"10.1007\/BFb0035848"},{"key":"27_CR7","volume-title":"Succinct representation of graphs","author":"H. Galperin","year":"1982","unstructured":"H. Galperin, Succinct representation of graphs, Ph.D. Thesis, Department of EECS Princeton University, Princeton N.J. (1982)"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"A. Habel, H.J. Kreowski, \u201dMay we introduce to you: Hypergraph Languages Generated by Edge Replacement,\u201d Graph-Grammars and Their Application to Computer Science (H. Ehrig, A. Rosenfeld, G. Rozenberg, eds.), Springer Lecture Notes in Computer Science No. 291 (1987)","DOI":"10.1007\/3-540-18771-5_41"},{"key":"27_CR9","unstructured":"A. Habel, H.J. Kreowski, \u201dSome structural aspects of hypergraph languages generated by hyperedge replacement,\u201d Proceedings of STACS '87 (F.J. Brandenburg, G. Vidal-Naquet, M. Wirsing, eds.), Springer Lecture Notes in Computer Science No. 247, pp. 207\u2013219 (1987)"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"K. Iwona, K. Steiglitz, \u201dTesting for cycles in infinite graphs with periodic structure,\u201d Proceedings of 19th ACM STOC, pp. 46\u201355 (1987)","DOI":"10.1145\/28395.28401"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/0022-0000(81)90025-8","volume":"22","author":"D. Janssens","year":"1981","unstructured":"D. Janssens, G. Rozenberg, \u201dDecision problems for node label controlled graph grammars,\u201d Journal of Computer and System Sciences Vol. 22, pp. 144\u2013177 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"C. Lautemann, \u201dEfficient algorithms on context-free graph languages,\u201d to appear in Proceedings of ICALP '88, Springer Lecture Notes in Computer Science (1988)","DOI":"10.1007\/3-540-19488-6_128"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"T. Lengauer, \u201dHierarchical planarity testing algorithms,\u201d Proceedings of ICALP '86 (L. Kott, ed.), Springer Lecture Notes in Computer Science No. 226, pp. 215\u2013225 (1986)","DOI":"10.1007\/3-540-16761-7_71"},{"key":"27_CR14","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0196-6774(87)90042-3","volume":"8","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer, \u201dEfficient algorithms for finding minimum spanning forests of hierarchically defined graphs,\u201d Journal of Algorithms Vol. 8, pp. 260\u2013284 (1987)","journal-title":"Journal of Algorithms"},{"key":"27_CR15","unstructured":"T. Lengauer, K.W. Wagner, \u201dThe correlation between the complexities of the non-hierarchical and hierarchical version of graph problems,\u201d Proceedings of STACS '87 (F.J. Brandenburg, G. Vidal-Naquet, M. Wirsing, eds.), Springer Lecture Notes in Computer Science No. 247, pp. 100\u2013113 (1987)"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"T. Lengauer, E. Wanke, \u201dEfficient solution of connectivity problems on hierarchically defined graphs,\u201d to appear in SIAM Journal of Computing (1988)","DOI":"10.1137\/0217068"},{"key":"27_CR17","unstructured":"T. Lengauer, E. Wanke, Efficient analysis of graph properties on context-free graph languages, Universit\u00e4t-GH Paderborn Fachbereich 17, Informatik Bericht No. 45 (1987)"},{"key":"27_CR18","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1137\/0213040","volume":"13","author":"J.Y.-T. Leung","year":"1984","unstructured":"J.Y.-T. Leung, O. Vornberger, J. Witthof, \u201dOn some variations of the bandwidth minimization problem,\u201d SIAM Journal of Computing Vol. 13, pp. 650\u2013667 (1984)","journal-title":"SIAM Journal of Computing"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"M.G. Main, G. Rozenberg, \u201dEdge-label controlled graph grammars,\u201d Graph-Grammars and Their Application to Computer Science (H. Ehrig, A. Rosenfeld, G. Rozenberg, eds.), Springer Lecture Notes in Computer Science No. 291 (1987)","DOI":"10.1007\/3-540-18771-5_67"},{"key":"27_CR20","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","volume":"69","author":"G. Rozenberg","year":"1986","unstructured":"G. Rozenberg, E. Welzl, \u201dBoundary NLC graph grammars \u2014 basic definitions, normal forms, and complexity,\u201d Information and Control Vol. 69, pp. 136\u2013167 (1986)","journal-title":"Information and Control"},{"key":"27_CR21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF00289115","volume":"23","author":"G. Rozenberg","year":"1986","unstructured":"G. Rozenberg, E. Welzl, \u201dGraph theoretic closure properties of the family of boundary NLC graph languages,\u201d Acta Informatica Vol. 23, pp. 289\u2013309 (1986)","journal-title":"Acta Informatica"},{"key":"27_CR22","unstructured":"G. Rozenberg, personal communication."},{"key":"27_CR23","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0020-0190(82)90086-2","volume":"14","author":"A.O. Slisenko","year":"1982","unstructured":"A.O. Slisenko, \u201dContext-free grammars as a tool for describing polynomial-time subciasses of hard problems,\u201d Information Processing Letters Vol. 14, pp. 52\u201356 (1982)","journal-title":"Information Processing Letters"},{"issue":"3","key":"27_CR24","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, N. Saito, \u201dLinear-time computability of combinatorial problems on series-parallel graphs,\u201d Journal of the ACM Vol. 29, No. 3, pp. 623\u2013641 (1982)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:44:40Z","timestamp":1742589880000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_129","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}