Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T06:33:25.612Z Has data issue: false hasContentIssue false

Counting Unlabelled Subtrees of a Tree is #P-complete

Published online by Cambridge University Press:  01 February 2010

Leslie Ann Goldberg
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, leslie@dcs.warwick.ac.uk, http://www.dcs.warwick.ac.uk/~leslie/
Mark Jerrum
Affiliation:
Department of Computer Science, University of Edinburgh, The King's Buildings, Edinburgh EH9 3JZ, mrj@dcs.ed.ac.uk, http://www.dcs.ed.ac.uk/~mrj/

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2000