{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:25:17Z","timestamp":1726406717823},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_39","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:40:56Z","timestamp":1330263656000},"page":"33-44","source":"Crossref","is-referenced-by-count":0,"title":["Bounded tree-width and LOGCFL"],"prefix":"10.1007","author":[{"given":"Egon","family":"Wanke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8(2):227\u2013284, April 1987.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"4_CR2","series-title":"volume 532 of Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/BFb0017382","volume-title":"Graph-Grammars and Their Application to Computer Science","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. In H. Ehrig, H.J. Kreowski, and G. Rozenberg, editors, Graph-Grammars and Their Application to Computer Science, volume 532 of Lecture Notes in Computer Science, pages 70\u201383. Springer-Verlag, Berlin\/New York, 1991. To appear in Journal of the ACM."},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Problems easy for tree-decomposable graphs. Journal of Algorithms, 12:308\u2013340, 1991.","journal-title":"Journal of Algorithms"},{"key":"4_CR4","first-page":"1","volume-title":"volume 344 of Lecture Notes in Computer Science","author":"H. L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender. NC-algorithms for graphs with bounded tree-width. In J. van Leeuwen, editor, Proceedings of Graph-Theoretical Concepts in Computer Science, volume 344 of Lecture Notes in Computer Science, pages 1\u201310. Springer-Verlag, Berlin\/New York, 1988."},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Annual ACM Symposium on Theory of Computing, 1993.","DOI":"10.1145\/167088.167161"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M.L. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal of Computing, 18:559\u2013578, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A.K. Chandra, D.C. Kozen, and L.J. Stockmeyer. Alternation. Journal of the ACM, 28:114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"key":"4_CR8","unstructured":"N. Chandrasekharan and A. Hedetniemi. Fast parallel algorithms for tree decomposition and parsing partial k-trees. In 26th Annual Allerton Conference on Communication, Control, and Computing, 1988."},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"4_CR10","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. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979."},{"issue":"4","key":"4_CR11","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal of Computing, 16(4):760\u2013778, August 1987.","journal-title":"SIAM Journal of Computing"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"J. Lagergren. Efficient parallel algorithms for tree-decomposition and related problems. In Annual ACM Symposium on Foundations of Computer Science, pages 218\u2013223. IEEE, 1990.","DOI":"10.1109\/FSCS.1990.89536"},{"issue":"6","key":"4_CR13","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke. Efficient solution of connectivity problems on hierarchically defined graphs. SIAM Journal of Computing, 17(6):1063\u20131080, December 1988.","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"4_CR14","first-page":"368","volume":"40","author":"T. Lengauer","year":"1993","unstructured":"T. Lengauer and E. Wanke. Efficient analysis of graph properties on context-free graph languages. Journal of the A CM, 40(2):368\u2013393, 1993.","journal-title":"Journal of the A CM"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"B. Reed. Finding approximate separators and computing tree width quickly. In Annual ACM Symposium on Theory of Computing, pages 221\u2013228, 1992.","DOI":"10.1145\/129712.129734"},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors II. Algorithmic aspects of tree width. Journal of Algorithms, 7:309\u2013322, 1986.","journal-title":"Journal of Algorithms"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"W.L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21:218\u2013235, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR18","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I.H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25:405\u2013414, 1978.","journal-title":"Journal of the ACM"},{"issue":"1","key":"4_CR19","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(91)90035-Z","volume":"94","author":"E. Wanke","year":"1991","unstructured":"E. Wanke. Algorithms for graph problems on BNLC structured graphs. Information and Computation, 94(1):93\u2013122, September 1991.","journal-title":"Information and Computation"},{"key":"4_CR20","unstructured":"E. Wanke. k-NLC graphs and polynomial algorithms. Special Issue in Annals of Discrete Mathematics, 1993. To appear."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:09:35Z","timestamp":1619572175000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}