Given a *query* q and a *relational structure* D the *enumeration *of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The *delay* is the maximal time between two consecutive output and the *preprocessing time* is the time needed to produce the first solution. Idealy, we would like to have *constant delay enumeration after linear preprocessing. *Since this it is not always possible to achieve, we need to add restriction to the classes of structures and/or queries we consider.

In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries...

We will more specifically consider *nowhere dense* classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

Oct 28, 2019 | 02:15 PM

Humboldt-Universität zu Berlin

Institut für Informatik

Room 3.408 (House 3 / 4th Floor [British Reading])

Johann von Neumann-Haus

Rudower Chaussee 25

12489 Berlin