We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O?(1.8494m) time for 3-regular graphs, and O?(1.9706m) time for unit interval graphs, where m is the number of edges in the graph and O?-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation. |
| Cite as: Gebauer, H. and Okamoto, Y. (2007). Fast Exponential-Time Algorithms for the Forest Counting in Graph Classes. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 63-69. |
 (from crpit.com)
(local if available)
|