Czasopismo
2014
|
Vol. 130, nr 4
|
415--421
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
We provide an algorithm for listing all minimal double dominating sets of a tree of order n in time O(1.3248n). This implies that every tree has at most 1.3248n minimal double dominating sets. We also show that this bound is tight.
Czasopismo
Rocznik
Tom
Strony
415--421
Opis fizyczny
Bibliogr. 13 poz.
Twórcy
autor
- Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Poland, marcin.krzywkowski@gmail.com
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-63357f9d-ba4a-4bef-b017-022c04057b5f