Monday, April 24, 2017
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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.
Colloquium - 16:00
Abstract: