Geodesic
Minimal 2-dominating sets in trees
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 235-240

Voir la notice de l'article provenant de la source Numdam

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time 𝒪(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.

DOI : 10.1051/ita/2013036
Classification : 05C05, 05C69, 05C85, 68R10, 68W05
Keywords: domination, 2-domination, minimal 2-dominating set, tree, counting, exact exponential algorithm, listing algorithm 
@article{ITA_2013__47_3_235_0,
     author = {Krzywkowski, Marcin},
     title = {Minimal 2-dominating sets in trees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {235--240},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {3},
     year = {2013},
     doi = {10.1051/ita/2013036},
     mrnumber = {3103126},
     zbl = {1282.05179},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013036/}
}
TY  - JOUR
AU  - Krzywkowski, Marcin
TI  - Minimal 2-dominating sets in trees
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2013
SP  - 235
EP  - 240
VL  - 47
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013036/
DO  - 10.1051/ita/2013036
LA  - en
ID  - ITA_2013__47_3_235_0
ER  - 
%0 Journal Article
%A Krzywkowski, Marcin
%T Minimal 2-dominating sets in trees
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2013
%P 235-240
%V 47
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013036/
%R 10.1051/ita/2013036
%G en
%F ITA_2013__47_3_235_0
Krzywkowski, Marcin. Minimal 2-dominating sets in trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 235-240. doi: 10.1051/ita/2013036

Cité par Sources :