Search
Abstract
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.
Citations
-
1 5
CrossRef
-
0
Web of Science
-
1 6
Scopus
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
INFORMATION PROCESSING LETTERS
no. 113,
pages 276 - 279,
ISSN: 0020-0190 - Language:
- English
- Publication year:
- 2013
- Bibliographic description:
- Krzywkowski M.: Trees having many minimal dominating sets// INFORMATION PROCESSING LETTERS. -Vol. 113, nr. 8 (2013), s.276-279
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.ipl.2013.01.020
- Verified by:
- Gdańsk University of Technology
seen 122 times