[Facets-of-complexity] Invitation to Monday's Lecture Jan.24 - online via Zoom.

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture will take place online via Zoom on January 24.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!

You all are cordially invited!

Location:

Online via Zoom.

Monday's Lecture: Günter Rote (Freie Universität Berlin)

Time: Monday, January 24 - 14:15 h

Title: The maximum number of minimal dominating sets in a tree

Abstract:

A tree with n vertices has at most 95^n/13 minimal dominating sets. The growth constant λ=¹³√95≈1.4194908 is best possible. It is obtained in a semi-automatic way as a kind of "dominant eigenvalue" of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises interesting questions about the "growth" of a general bilinear operation.

We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

You all are cordially invited!

Virenfrei. www.avast.com