Minimal 2-dominating sets in trees

Marcin Krzywkowski

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 3, page 235-240
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Krzywkowski, Marcin. "Minimal 2-dominating sets in trees." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.3 (2013): 235-240. <http://eudml.org/doc/273012>.

@article{Krzywkowski2013,
abstract = {We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time &#x1d4aa;(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.},
author = {Krzywkowski, Marcin},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {domination; 2-domination; minimal 2-dominating set; tree; counting; exact exponential algorithm; listing algorithm},
language = {eng},
number = {3},
pages = {235-240},
publisher = {EDP-Sciences},
title = {Minimal 2-dominating sets in trees},
url = {http://eudml.org/doc/273012},
volume = {47},
year = {2013},
}

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
PB - EDP-Sciences
VL - 47
IS - 3
SP - 235
EP - 240
AB - We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time &#x1d4aa;(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.
LA - eng
KW - domination; 2-domination; minimal 2-dominating set; tree; counting; exact exponential algorithm; listing algorithm
UR - http://eudml.org/doc/273012
ER -

References

top
  1. [1] A. Björklund and T. Husfeldt, Inclusion-exclusion algorithms for counting set partitions. Proc. of FOCS (2006) 575–582. 
  2. [2] M. Blidia, O. Favaron and R. Lounes, Locating-domination, 2-domination and independence in trees. Australas. J. Combin. 42 (2008) 309–316. Zbl1153.05039MR2445823
  3. [3] D. Bród and Z. Skupień, Trees with extremal numbers of dominating sets. Australas. J. Combin.35 (2006) 273–290. Zbl1094.05017MR2239321
  4. [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. Zbl1219.05113MR2674931
  5. [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. Zbl1298.05246MR2958175
  6. [6] D. Eppstein, Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl.7 (2003) 131–140. Zbl1027.05092MR2112051
  7. [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. Zbl0573.05049MR812671
  8. [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). MR2479180
  9. [9] F. Fomin and D. Kratsch, Exact Exponential Algorithms. Springer, Berlin (2010). Zbl05817382MR3234973
  10. [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. Zbl1147.05052MR2381434
  11. [11] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). Zbl0883.00011MR1605684
  12. [12] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). Zbl0883.00011MR1605685
  13. [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. Zbl05940784MR2886915
  14. [14] M. Koivisto, An &#x1d4aa;(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. [15] E. Lawler, A note on the complexity of the chromatic number problem. Information Proc. Lett.5 (1976) 66–67. Zbl0336.68021MR464675
  16. [16] J. Moon and L. Moser, On cliques in graphs. Israel J. Math.3 (1965) 23–28. Zbl0144.23205MR182577
  17. [17] R. Shaheen, Bounds for the 2-domination number of toroidal grid graphs. Internat. J. Comput. Math.86 (2009) 584–588. Zbl1162.05036MR2514154
  18. [18] H. Wilf, The number of maximal independent sets in a tree. SIAM J. Algebr. Discrete Methods7 (1986) 125–130. Zbl0584.05024MR819714

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.