{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T18:32:13Z","timestamp":1773081133419,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01758777","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:49:08Z","timestamp":1118832548000},"page":"555-581","source":"Crossref","is-referenced-by-count":178,"title":["Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families"],"prefix":"10.1007","volume":"7","author":[{"given":"Richard B.","family":"Borie","sequence":"first","affiliation":[]},{"given":"R. Gary","family":"Parker","sequence":"additional","affiliation":[]},{"given":"Craig A.","family":"Tovey","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01758777_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability,BIT,25 (1985), 2\u201323.","journal-title":"BIT"},{"key":"BF01758777_CR2","doi-asserted-by":"crossref","first-page":"277","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 ak-tree,SIAM Journal of Algebraic and Discrete Methods,8 (1987), 277\u2013284.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"BF01758777_CR3","first-page":"38","volume-title":"Lecture Notes in Computer Science, Vol. 317","author":"A. Arnborg","year":"1988","unstructured":"A. Arnborg, J. Lagergren, and D. Seese, Problems easy for tree-decomposable graphs, (extended abstract)Proceedings of the 15th ICALP, Lecture Notes in Computer Science, Vol. 317. Springer-Verlag, Berlin (1988), pp. 38\u201351; to appear inJournal of Algorithms."},{"key":"BF01758777_CR4","volume-title":"Linear time algorithms forNP-hard problems on graphs embedded ink-trees","author":"A. Arnborg","year":"1984","unstructured":"A. Arnborg and A. Proskurowski, Linear time algorithms forNP-hard problems on graphs embedded ink-trees, TRITA-NA-8404, Royal Institute of Technology, Sweden (1984)."},{"key":"BF01758777_CR5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"M. Bauderon and B. Courcelle, Graph expressions and graph rewritings,Mathematical Systems Theory,20 (1987), 83\u2013127.","journal-title":"Mathematical Systems Theory"},{"key":"BF01758777_CR6","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, and A. L. Wong, Linear time computation of optimal subgraphs of decomposable graphs,Jornal of Algorithms,8 (1987), 216\u2013235.","journal-title":"Jornal of Algorithms"},{"key":"BF01758777_CR7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, Dynamic programming on graphs with bounded tree-width, Technical report, Laboratory for Computer Science,M.I.T. (1987); extended abstract inProceedings of ICALP (1988).","DOI":"10.1007\/3-540-19488-6_110"},{"key":"BF01758777_CR8","unstructured":"H. L. Bodlaender, Planar graphs with bounded tree-width, RUU-CS-88-14, University of Utrecht (1988)."},{"key":"BF01758777_CR9","first-page":"1","volume-title":"Lecture Notes in Computer Science, Vol. 344","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender,NC-algorithms for graphs with small treewidth,Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (J. van Leeuwen, ed.) (1988), Lecture Notes in Computer Science, Vol. 344, Springer-Verlag, Berlin (1988), pp. 1\u201310."},{"key":"BF01758777_CR10","unstructured":"H. L. Bodlaender, Polynomial algorithms for graph isomorphism and chromatic index on partialk-trees,Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (1988), pp. 223\u2013232."},{"key":"BF01758777_CR11","unstructured":"B. Courcelle, Recognizability and second-order definability for sets of finitegraphs, Report 1-8634, Universite de Bordeaux (1987)."},{"key":"BF01758777_CR12","unstructured":"B. Courcelle, An algebraic and logical theory of graphs, a survey, unpublished manuscript (1988)."},{"key":"BF01758777_CR13","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey, R. L. Graham, D. S. Johnson, and D. E. Knuth, Complexity results for bandwidth minimization,SIAM Journal of Applied Mathematics,34 (1978), 477\u2013495.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"BF01758777_CR14","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability, Freeman, San Francisco (1979)."},{"key":"BF01758777_CR15","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson, TheNP-completeness column: an ongoing guide,Journal of Algorithms,6 (1985), 434\u2013451.","journal-title":"Journal of Algorithms"},{"key":"BF01758777_CR16","unstructured":"S. Mahajan and J. G. Peters, Algorithms for regular properties in recursive graphs,Proceedings of the 25th Annual Allerton Conference on Communications, Control, and Computing (1987), pp. 14\u201323."},{"key":"BF01758777_CR17","unstructured":"R. L. Rardin and R. G. Parker, Tree subgraph isomorphism isNP-complete on series-parallel graphs, unpublished manuscript (1985)."},{"key":"BF01758777_CR18","unstructured":"M. B. Richey, Combinatorial optimization on series-parallel graphs: algorithms and complexity, Ph.D. Thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (1985)."},{"key":"BF01758777_CR19","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T. Schaefer","year":"1978","unstructured":"T. Schaefer, Complexity of some two-person perfect information games,Journal of Computer and System Sciences,16 (1978), 185\u2013225.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01758777_CR20","unstructured":"P. Scheffler and D. Seese, A combinatorial and logical approach to linear-time computability, extended abstract (1986)."},{"key":"BF01758777_CR21","doi-asserted-by":"crossref","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), 91\u201397.","journal-title":"Theoretical Computer Science"},{"key":"BF01758777_CR22","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs,Journal of the Association for Computing Machinery,29 (1982), 623\u2013641.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01758777_CR23","unstructured":"T. V. Wimer, Linear algorithms onk-terminal graphs, Ph.D. Thesis, Report No. URI-030, Clemson University (1987)."},{"key":"BF01758777_CR24","first-page":"43","volume":"50","author":"T. V. Wimer","year":"1985","unstructured":"T. V. Wimer, S. T. Hedetniemi, and R. Laskar, A methodology for constructing linear graph algorithms,Congressus Numerantium,50 (1985), 43\u201360.","journal-title":"Congressus Numerantium"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758777.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758777\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T18:57:22Z","timestamp":1586285842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":24,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758777"],"URL":"https:\/\/doi.org\/10.1007\/bf01758777","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}