Geodesic
Counting Stable Sets in Trees
Séminaire lotharingien de combinatoire, Tome 10 (1984)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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
  1. prove that the problem of counting all stable sets in a tree is no harder than listing all maxima! stable sets in a tree
  2. calculate the upper bound on the number of maxima) stable sets in a tree of n vertices. 
@article{SLC_1984_10_a11,
     author = {Daniel I. A. Cohen},
     title = {Counting {Stable} {Sets} in {Trees}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {10},
     year = {1984},
     url = {http://geodesic.mathdoc.fr/item/SLC_1984_10_a11/}
}
TY  - JOUR
AU  - Daniel I. A. Cohen
TI  - Counting Stable Sets in Trees
JO  - Séminaire lotharingien de combinatoire
PY  - 1984
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1984_10_a11/
ID  - SLC_1984_10_a11
ER  - 
%0 Journal Article
%A Daniel I. A. Cohen
%T Counting Stable Sets in Trees
%J Séminaire lotharingien de combinatoire
%D 1984
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1984_10_a11/
%F SLC_1984_10_a11
Daniel I. A. Cohen. Counting Stable Sets in Trees. Séminaire lotharingien de combinatoire, Tome 10 (1984). http://geodesic.mathdoc.fr/item/SLC_1984_10_a11/