Query enumeration and nowhere dense classes of graphs

Prelegent(ci)

Alexandre Vigny

Afiliacja

Uniwersytet Warszawski

Termin

5 grudnia 2018 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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?

---