Abstract:
The problem of counting unlabelled subtrees of a tree (i.e., subtrees that are distinct up to isomorphism) is #P-complete, and hence equivalent in computational diffculty to evaluating the permanent of a 0,1-matrix.
ECS-LFCS-99-417.
This report is available in the following formats: