An Algorithm for Listing all Minimal Double Dominating Sets of a Tree

• Autorzy: Krzywkowski M.

Identyfikatory

DOI

10.3233/FI-2014-998

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

domination, double domination; minimal double dominating set; tree; combinatorial bound; exact exponential algorithm; listing algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 4
• Strony: 415--421
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Krzywkowski M.

• Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Poland
• Institute of Mathematics, Polish Academy of Sciences

Bibliografia

• [1] D. Bród and Z. Skupień, Trees with extremal numbers of dominating sets, Australasian Journal of Combinatorics 35 (2006), 273–290.
• [2] D. Bród, A. Włoch, and I. Włoch, On the number of minimal dominating sets including the set of leaves in trees, International Journal of Contemporary Mathematical Sciences 4(2009), 1739–1748.
• [3] J.-F. Couturier, P. Heggernes, P. van ’t Hof, and D. Kratsch, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Proceedings of SOFSEM 2012, 202–213, Lecture Notes in Computer Science, 7147, Springer-Verlag, Berlin, 2012.
• [4] 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 5 (2009), article 9, 17 pp.
• [5] F. Fomin and D. Kratsch, Exact Exponential Algorithms, Springer, Berlin, 2010.
• [6] F. Harary and T. Haynes, Double domination in graphs, Ars Combinatoria 55 (2000), 201-213.
• [7] T. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [8] T. Haynes, S. Hedetniemi, and P. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [9] M. Kanté, V. Limouzy, A. Mary, and L. Nourine, Enumeration of minimal dominating sets and variants, Fundamentals of computation theory, 298–309, Lecture Notes in Computer Science, 6914, Springer, Heidelberg, 2011.
• [10] M. Krzywkowski, Trees having many minimal dominating sets, Information Processing Letters 113 (2013), 276–279.
• [11] E. Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters 5 (1976), 66–67.
• [12] J. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics 3 (1965), 23–28.
• [13] H. Wilf, The number of maximal independent sets in a tree, SIAM Journal on Algebraic and DiscreteMethods 7 (1986), 125–130.