Wyszukiwarka
Abstrakt
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.
Cytowania
-
1 5
CrossRef
-
0
Web of Science
-
1 6
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
INFORMATION PROCESSING LETTERS
nr 113,
strony 276 - 279,
ISSN: 0020-0190 - Język:
- angielski
- Rok wydania:
- 2013
- Opis bibliograficzny:
- Krzywkowski M.: Trees having many minimal dominating sets// INFORMATION PROCESSING LETTERS. -Vol. 113, nr. 8 (2013), s.276-279
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.ipl.2013.01.020
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 168 razy