Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• dr inż. Marcin Krzywkowski link otwiera się w nowej karcie