Counting trees in a graph is \(\# \text{P}\)-complete

DOI10.1016/0020-0190(94)00085-9zbMath0809.68076OpenAlexW2053566189WikidataQ56083439 ScholiaQ56083439MaRDI QIDQ1332763

Mark R. Jerrum

Publication date: 13 October 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00085-9

zbMATH Keywords

computational complexitycombinatorial enumeration\#P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

Related Items (5)

Parameterized counting of trees, forests and matroid bases ⋮ Models of random subtrees of a graph ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Approximately counting paths and cycles in a graph ⋮ Parameterized counting of partially injective homomorphisms

Cites Work

• The Complexity of Enumeration and Reliability Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unnamed Item

This page was built for publication: Counting trees in a graph is \(\# \text{P}\)-complete