Counting trees in a graph is \# P-complete
From MaRDI portal
Publication:1332763
DOI10.1016/0020-0190(94)00085-9zbMATH Open0809.68076OpenAlexW2053566189WikidataQ56083439 ScholiaQ56083439MaRDI QIDQ1332763FDOQ1332763
Authors: Mark 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)
Cites Work
Cited In (15)
- A note on a counting problem arising in percolation theory
- Title not available (Why is that?)
- Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
- Approximately counting paths and cycles in a graph
- Counting Unlabelled Subtrees of a Tree is #P-complete
- Counting consistent phylogenetic trees is \#P-complete
- Counting trees in a phylogenetic network is \#P-complete
- Some problems on approximate counting in graphs and matroids
- Parameterized counting of trees, forests and matroid bases
- Parameterized counting of partially injective homomorphisms
- Computational complexity of counting coincidences
- Models of random subtrees of a graph
- Space-efficient counting in graphs on surfaces
- Counting polygon triangulations is hard
- The complexity of counting homeomorphs
This page was built for publication: Counting trees in a graph is \(\# \text{P}\)-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332763)
