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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2013036/
[1] Inclusion-exclusion algorithms for counting set partitions. Proc. of FOCS (2006) 575-582.
and ,[2] Locating-domination, 2-domination and independence in trees. Australas. J. Combin. 42 (2008) 309-316. | MR | Zbl
, and ,[3] Trees with extremal numbers of dominating sets. Australas. J. Combin. 35 (2006) 273-290. | MR | Zbl
and ,[4] 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
, and ,[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] Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl. 7 (2003) 131-140. | EuDML | MR | Zbl
,[7] n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 282−300. | MR | Zbl
and ,[8] Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Transactions on Algorithms, vol. 5, article 9 (2009). | MR
, , and ,[9] Exact Exponential Algorithms. Springer, Berlin (2010). | MR
and ,[10] Independence and 2-domination in bipartite graphs. Australas. J. Combin. 40 (2008) 265-268. | MR | Zbl
, , , , and ,[11] Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR | Zbl
, and ,[12] Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). | MR | Zbl
, and ,[13] Enumeration of minimal dominating sets and variants, Fundamentals of computation theory. Lect. Notes Comput. Sci., vol. 6914. Springer, Heidelberg (2011) 298-309. | MR
, , and ,[14] 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] A note on the complexity of the chromatic number problem. Information Proc. Lett. 5 (1976) 66-67. | MR | Zbl
,[16] On cliques in graphs. Israel J. Math. 3 (1965) 23-28. | MR | Zbl
and ,[17] Bounds for the 2-domination number of toroidal grid graphs. Internat. J. Comput. Math. 86 (2009) 584-588. | MR | Zbl
,[18] The number of maximal independent sets in a tree. SIAM J. Algebr. Discrete Methods 7 (1986) 125-130. | MR | Zbl
,Cité par Sources :