{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:01:22Z","timestamp":1768705282592,"version":"3.49.0"},"reference-count":12,"publisher":"Wiley","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"unspecified","delay-in-days":3684,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2000]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of counting unlabelled subtrees of a tree (that is, sub-trees that are distinct up to isomorphism) is #P-complete, and hence equivalent in computational difficulty to evaluating the permanent of a 0,1-matrix.<\/jats:p>","DOI":"10.1112\/s1461157000000243","type":"journal-article","created":{"date-parts":[[2010,10,21]],"date-time":"2010-10-21T15:22:57Z","timestamp":1287674577000},"page":"117-124","source":"Crossref","is-referenced-by-count":6,"title":["Counting Unlabelled Subtrees of a Tree is #P-complete"],"prefix":"10.1112","volume":"3","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2010,2,1]]},"reference":[{"key":"S1461157000000243_ref006","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"S1461157000000243_ref010","first-page":"205\u2018221","article-title":"\u2018Polynomial-time 1-Turing reductions from #PH to #P\u2019","volume":"100","author":"Toda","year":"1992","journal-title":"Theoret. Comput. Set"},{"key":"S1461157000000243_ref003","unstructured":"3. Garey M. R. and Johnson D. S. , Computers and intractability: a guide to the theory of NP-completeness (Freeman, San Francisco, CA, 1979)."},{"key":"S1461157000000243_ref012","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511752506"},{"key":"S1461157000000243_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00100-R"},{"key":"S1461157000000243_ref008","unstructured":"8. Papadimitriou C. H. , Computational complexity (Addison-Wesley, 1994)."},{"key":"S1461157000000243_ref011","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"S1461157000000243_ref009","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"S1461157000000243_ref007","first-page":"363","article-title":"\u2018On counting and approximation\u2019","volume":"26","author":"K\u00f6bler","year":"1989","journal-title":"Acta In form."},{"key":"S1461157000000243_ref004","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"S1461157000000243_ref005","volume-title":"Graphical enumeration","author":"Harary","year":"1973"},{"key":"S1461157000000243_ref001","unstructured":"1. Blache G. , Karpinski M. and Wirtgen J. , \u2018On approximation intractability of the bandwidth problem\u2019, Electronic Colloquium on Computational Complexity, Report TR98-014, 1998. http:\/\/www.eccc.uni-trier.de\/eccc-local\/Lists\/TR-1998.html"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157000000243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T23:49:11Z","timestamp":1559951351000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157000000243\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"references-count":12,"alternative-id":["S1461157000000243"],"URL":"https:\/\/doi.org\/10.1112\/s1461157000000243","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000]]}}}