Home
 

Counting unlabelled subtrees of a tree is #P-complete

Leslie Ann Goldberg and Mark Jerrum

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:

Previous | Index