BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Given a query q and a relational structure D the enumerat
ion 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 produ
ce the first solution. Idealy\, we would like to have constant delay enume
ration after linear preprocessing. Since this it is not always possible to
achieve\, we need to add restriction to the classes of structures and/or q
ueries we consider. In this talk I will talk about some restrictions for
which such algorithms exist: graphs with bounded degree\, tree-like struct
ures\, conjunctive queries... We will more specifically consider nowhere
dense classes of graphs: What are they? Why is this notion relevant? How t
o make algorithms from these graph properties?
DTSTAMP:20191025T163100
DTSTART:20191028T141500
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Humbold
t-Kabinett (between House 3&4 / 1st Floor [British Reading])\n Johann von N
eumann-Haus\n Rudower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Alexandre Vigny (Universität Bremen): Query enumeration and nowhere
dense classes of graphs
UID:95691444@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20191028-L-Vigny.html
END:VEVENT
END:VCALENDAR