This paper studied the problems of counting independent sets, maximal independent sets, and maximum independent sets of a graph from an algorithmic point of view. In particular, we present linear-time algorithms for these problems in trees and unicyclic graphs.
Citation
Min-Jen Jou, Gerard J.Chang. Algorithmic Aspects of Counting Independent Sets[J], Ars Combinatoria, Volume 065. 265-277. .