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