Lecture by Alexandre Vigny (Universität Bremen): Query enumeration and nowhere dense classes of graphs

Oct 28, 2019 | 02:15 PM

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?

Time & Location

Oct 28, 2019 | 02:15 PM

Humboldt-Universität zu Berlin
Institut für Informatik
Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading])
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)