{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T16:54:32Z","timestamp":1648918472902},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","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":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994877","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T20:22:09Z","timestamp":1123186929000},"page":"197-214","source":"Crossref","is-referenced-by-count":7,"title":["Canonical representations of partial 2- and 3-trees"],"prefix":"10.1007","volume":"32","author":[{"given":"Stefan","family":"Arnborg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Proskurowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994877_CR1","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ullman,Design and Analysis of Computer Algorithms, Addison-Wesley (1972)."},{"key":"BF01994877_CR2","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 \u2014 a survey, BIT 25(1985), 2\u201333.","journal-title":"BIT"},{"key":"BF01994877_CR3","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 a k-tree, SIAM J. Alg. and Discr. Methods 8(1987), 277\u2013287.","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"BF01994877_CR4","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski and D. Seese,An algebraic theory of graph reduction, submitted."},{"key":"BF01994877_CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski,Characterization and recognition of partial 3-trees, SIAM J. Alg. and Discr. Methods 7(1986), 305\u2013314.","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"BF01994877_CR6","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski,Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discr. Appl. Math. 23(1989), 11\u201324.","journal-title":"Discr. Appl. Math."},{"key":"BF01994877_CR7","first-page":"227","volume":"318","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender,Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Proceedings of SWAT'88, Springer-Verlag LNCS 318(1988), 227\u2013232.","journal-title":"Proceedings of SWAT'88, Springer-Verlag LNCS"},{"key":"BF01994877_CR8","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U. S. R. Murty,Graph Theory with Application, North Holland (1976).","DOI":"10.1007\/978-1-349-03521-2"},{"key":"BF01994877_CR9","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/0020-0190(80)90149-0","volume":"10","author":"K. S. Booth","year":"1980","unstructured":"K. S. Booth,Finding a lexicographic least shift of a string, Information Processing Letters 10(1980), 240\u2013242.","journal-title":"Information Processing Letters"},{"key":"BF01994877_CR10","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"C. J. Colbourn","year":"1981","unstructured":"C. J. Colbourn and K. S. Booth,Linear time automorphism algorithms for trees, interval graphs, and planar graphs, SIAM J. Computing 10(1981), 203\u2013225.","journal-title":"SIAM J. Computing"},{"key":"BF01994877_CR11","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(1990), 12\u201375.","journal-title":"Information and Computation"},{"key":"BF01994877_CR12","doi-asserted-by":"crossref","unstructured":"I. S. Filotti and J. N. Mayer,A polynomial-time algorithm for determining the isomorphism of graphs of bounded genus, Proc. 12th ACM Symp. on Theory of Computing (1980), 236\u2013243.","DOI":"10.1145\/800141.804671"},{"key":"BF01994877_CR13","unstructured":"M. Fontet,A linear algorithm for testing isomorphism of planar graphs, Proc. 3rd Int. Conf. Automata, Languages, Programming, Springer-Verlag LNCS (1976), 1411\u2013423."},{"key":"BF01994877_CR14","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability, W. H. Freeman and Company, San Francisco (1979)."},{"key":"BF01994877_CR15","doi-asserted-by":"crossref","unstructured":"J. E. Hopcroft and J. K. Wong,A linear time algorithm for isomorphism of planar graphs, Proc. 6th ACM Symp. Theory of Computer Science (1974), 172\u2013184.","DOI":"10.1145\/800119.803896"},{"key":"BF01994877_CR16","doi-asserted-by":"crossref","unstructured":"J. Lagergren,Efficient parallel algorithms for tree-decomposition and related problems. Proceedings of IEEE FoCS 1990.","DOI":"10.1109\/FSCS.1990.89536"},{"key":"BF01994877_CR17","unstructured":"J. Lagergren,The non-existence of reduction rules giving an embedding in a k-tree, to appear inAnnals of Discrete Mathematics."},{"key":"BF01994877_CR18","first-page":"42","volume":"25","author":"E. M. Luks","year":"1982","unstructured":"E. M. Luks,Isomorphism of graphs of bounded valence can be tested in polynomial time, JCSS 25(1982), 42\u201365.","journal-title":"JCSS"},{"key":"BF01994877_CR19","doi-asserted-by":"crossref","unstructured":"G. L. Miller,Isomorphism testing for graphs with bounded genus, Proc. 12th ACM Symp. on Theory of Computing (1980), 225\u2013235.","DOI":"10.1145\/800141.804670"},{"key":"BF01994877_CR20","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/3-540-12689-9_114","volume":"158","author":"G. L. Miller","year":"1983","unstructured":"G. L. Miller,Isomorphism testing and canonical forms for k-contractible graphs, Proc. Foundations of Computation Theory, Springer-Verlag LNCS 158 (1983), 310\u2013327.","journal-title":"Proc. Foundations of Computation Theory, Springer-Verlag LNCS"},{"key":"BF01994877_CR21","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/0210028","volume":"10","author":"A. Proskurowski","year":"1981","unstructured":"A. Proskurowski,Recursive graphs, recursive labelings and shortest paths, SIAM J. Computing 10(1981), 391\u2013397.","journal-title":"SIAM J. Computing"},{"key":"BF01994877_CR22","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0012-365X(84)90164-X","volume":"49","author":"A. Proskurowski","year":"1984","unstructured":"A. Proskurowski,Separating subgraphs in k-trees: cables and caterpillars, Discrete Mathematics 49(1984), 275\u2013285.","journal-title":"Discrete Mathematics"},{"key":"BF01994877_CR23","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. D. Seymour,Graph minors V, excluding a planar graph, J. Combinatorial Theory, Ser. B, 41(1986), 92\u2013114.","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"BF01994877_CR24","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0012-365X(74)90042-9","volume":"7","author":"D. J. Rose","year":"1970","unstructured":"D. J. Rose,On simple characterization of k-trees, Discrete Mathematics 7(1970), 317\u2013322.","journal-title":"Discrete Mathematics"},{"key":"BF01994877_CR25","unstructured":"J. J. Rotman,The Theory of Groups (2nd ed.), Allyn and Bacon (1973)."},{"key":"BF01994877_CR26","unstructured":"P. Scheffler,Linear time algorithms for NP-complete problems restricted to partial k-trees, Akad. Wiss. DDR Report R-MATH-03\/87 (1987)."},{"key":"BF01994877_CR27","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0020-0190(79)90114-5","volume":"8","author":"Y. Shiloah","year":"1979","unstructured":"Y. Shiloah,A fast equivalence-checking algorithm for circular lists, Information Processing Letters 8(1979), 236\u2013238.","journal-title":"Information Processing Letters"},{"key":"BF01994877_CR28","unstructured":"M. M. Syslo,Linear time algorithm for coding outerplanar graphs, in Beitr\u00e4ge zum Graphentheorie, Proceedings of Oberhof Conference 1977, H. Sachs (Ed.) (1978), 259\u2013269."},{"key":"BF01994877_CR29","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"A. Wald","year":"1983","unstructured":"A. Wald and C. J. Colbourn,Steiner trees, partial 2-trees, and minimum IFI networks, Networks 13(1983), 159\u2013167.","journal-title":"Networks"},{"key":"BF01994877_CR30","unstructured":"T. V. Wimer,Linear algorithms on k-terminal graphs, PhD. Thesis, Clemson University (1988)."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994877.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994877\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T17:37:10Z","timestamp":1586367430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994877"],"URL":"https:\/\/doi.org\/10.1007\/bf01994877","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}