We provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating sets of a given tree.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.ipl.2013.01.020
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2013
Source: MOSTWiedzy.pl - publication "Trees having many minimal dominating sets" link open in new tab
