Séminaire Lotharingien de Combinatoire, B10l (1984), 5 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-10, p.
48-52.]
Daniel I. A. Cohen
Counting Stable Sets in Trees
Abstract.
Cook [1] has shown that the problem of generating all the stable sets
of a given graph is NP complete while several authors have shown that
it is possible to generate all the maximal stable sets of G in
polynomial-time. In [3] this is done in
O(n = number of vertices, m = number of edges, μ = number of maximal stable sets).
In this paper we shall
-
prove that the problem of counting all stable sets in a tree is no harder than
listing all maxima! stable sets in a tree
- calculate the upper bound on the number of maxima) stable sets in a
tree of
n vertices.
The following version is available: