Search
Abstract
We provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- materiały konferencyjne indeksowane w Web of Science
- Title of issue:
- Proceedings of the 8th International Frontiers of Algorithmics Workshop strony 151 - 157
- ISSN:
- 0302-9743
- Language:
- English
- Publication year:
- 2014
- Bibliographic description:
- Krzywkowski M..: Minimal double dominating sets in trees, W: Proceedings of the 8th International Frontiers of Algorithmics Workshop, 2014, Springer,.
- Verified by:
- Gdańsk University of Technology
seen 97 times