Speaker:  Günter Rote, Freie Universität Berlin
Title: Minimal Dominating Sets in Trees: Counting, Enumeration, and Extremal Results
Time: 2:30 PM, Monday, February 26, 2018
Place:  Malott 206

Abstract: A tree with n vertices has at most 95^{n/13} minimal dominating sets. The corresponding growth constant 95^(1/13) ~ 1.4194908 is best possible. I will show how these results are obtained in a semi-automatic way with computer help, starting from the dynamic-programming recursion for computing the number of minimal dominating sets of a given tree. This recursion defines a bilinear operation on sixtuples, and the growth constant arises as a kind of "dominant eigenvalue" of this operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between reporting successive solutions. It is open whether the delay can be reduced to a constant delay, for an appropriate modification of the problem statement.


Back to main seminar page.