  We consider the problem of devising algorithms to count exactly the number of
independent sets of a graph G . We show that there is a polynomial time
algorithm for this problem when G is restricted to the class of strongly
orderable graphs, a superclass of chordal bipartite graphs. We also show that
such an algorithm exists for graphs of bounded clique-width. Our results
extends to a more general setting of counting independent sets in a weighted
graph and can be used to count the number of independent sets of any given size
k .
