An Algorithm for Listing all Minimal Double Dominating Sets of a Tree

作者：Krzywkowski Marcin^*

来源：Fundamenta Informaticae, 2014, 130(4): 415-421.

DOI：10.3233/FI-2014-998

• domination
• double domination
• minimal double dominating set
• tree
• combinatorial bound
• exact exponential algorithm
• listing algorithm

We provide an algorithm for listing all minimal double dominating sets of a tree of order n in time 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.

• 出版日期2014