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

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2013036/

[1] A. Björklund and T. Husfeldt, Inclusion-exclusion algorithms for counting set partitions. Proc. of FOCS (2006) 575-582.

[2] M. Blidia, O. Favaron and R. Lounes, Locating-domination, 2-domination and independence in trees. Australas. J. Combin. 42 (2008) 309-316. | MR | Zbl

[3] D. Bród and Z. Skupień, Trees with extremal numbers of dominating sets. Australas. J. Combin. 35 (2006) 273-290. | MR | Zbl

[4] D. Bród, A. Włoch and I. Włoch, On the number of minimal dominating sets including the set of leaves in trees. Internat. J. Contemporary Math. Sci. 4 (2009) 1739-1748. | MR | Zbl

[5] J.-F. Couturier, P. Heggernes, P. van 't Hof and D. Kratsch, Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Proc. of SOFSEM 2012, Lect. Notes Comput. Sci., vol. 7147. Springer-Verlag, Berlin (2012) 202-213. | MR | Zbl

[6] D. Eppstein, Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl. 7 (2003) 131-140. | EuDML | MR | Zbl

[7] J. Fink and M. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 282−300. | MR | Zbl

[8] F. Fomin, F. Grandoni, A. Pyatkin and A. Stepanov, Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Transactions on Algorithms, vol. 5, article 9 (2009). | MR

[9] F. Fomin and D. Kratsch, Exact Exponential Algorithms. Springer, Berlin (2010). | MR

[10] J. Fujisawa, A. Hansberg, T. Kubo, A. Saito, M. Sugita and L. Volkmann, Independence and 2-domination in bipartite graphs. Australas. J. Combin. 40 (2008) 265-268. | MR | Zbl

[11] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR | Zbl

[12] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). | MR | Zbl

[13] M. Kanté, V. Limouzy, A. Mary and L. Nourine, Enumeration of minimal dominating sets and variants, Fundamentals of computation theory. Lect. Notes Comput. Sci., vol. 6914. Springer, Heidelberg (2011) 298-309. | MR

[14] M. Koivisto, An 𝒪(2n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. Proc. 47th Annual IEEE Symposium on Foundations of Comput. Sci. (FOCS 2006), IEEE (2006) 583-590.

[15] E. Lawler, A note on the complexity of the chromatic number problem. Information Proc. Lett. 5 (1976) 66-67. | MR | Zbl

[16] J. Moon and L. Moser, On cliques in graphs. Israel J. Math. 3 (1965) 23-28. | MR | Zbl

[17] R. Shaheen, Bounds for the 2-domination number of toroidal grid graphs. Internat. J. Comput. Math. 86 (2009) 584-588. | MR | Zbl

[18] H. Wilf, The number of maximal independent sets in a tree. SIAM J. Algebr. Discrete Methods 7 (1986) 125-130. | MR | Zbl

Cité par Sources :