BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: While most NP-hard graph problems remain NP-hard when restrict
 ed to planar graphs\, they become somewhat simpler: they often admit algori
 thms with running time exponential in the square root of the size of the gr
 aph (or some other meaningful parameter). This behavior has been dubbed "th
 e square root phenomenon". For many problems\, such an algorithm follows fr
 om the theory of bidimensionality relying on a linear dependency on the siz
 e of the largest grid minor and treewidth of a planar graph. In recent year
 s we have seen a number of other algorithmic techniques\, significantly ext
 ending the boundary of the applicability of the "square root phenomenon". I
 n my talk I will survey this area and highlight main algorithmic approaches
 . 
DTSTAMP:20181112T183800
DTSTART:20181126T141500
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:Marcin Pilipczuk (University of Warsaw): The square root phenomenon
 : subexponential algorithms in sparse graph classes
UID:94535748@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181126-L-Pilipczuk.html
END:VEVENT
END:VCALENDAR