Query enumeration and nowhere dense classes of graphs

Speaker(s)

Alexandre Vigny

Affiliation

Uniwersytet Warszawski

Date

Dec. 5, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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?

---