Counting Unlabelled Subtrees of a Tree is #P-complete

DOI10.1112/S1461157000000243zbMath0951.68047MaRDI QIDQ4504966

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 25 September 2000

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.lms.ac.uk/jcm/3/lms1999-029/

zbMATH Keywords

counting unlabelled subtrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Algorithms for four variants of the exact satisfiability problem ⋮ Parameterized counting of partially injective homomorphisms ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

Cites Work

• Unnamed Item
• The complexity of harmonious colouring for trees
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Enumeration and Reliability Problems
• Efficient Planarity Testing
• Complexity Results for Bandwidth Minimization

This page was built for publication: Counting Unlabelled Subtrees of a Tree is #P-complete