| This paper is available as |  | (79 KB). |
Counting unlabelled subtrees of a tree is #P-completeAbstract: The problem of counting unlabelled subtrees of a tree (that is, subtrees that are distinct up to isomorphism) is #P-complete, and hence equivalent in computational difficulty to evaluating the permanent of a 0,1-matrix. |
| This paper is available as | | (79 KB). |
All papers published in the LMS JCM are covered by a copyright agreement with the authors. Access to the papers is bound by this agreement; click here for details.
Go to the Volume 3 index
Return to the LMS JCM Homepage