You are cordially invited to our Monday Lecture & Colloquium
on November 26th at 14:15 h & 16:00 h at HU Berlin. Location: Humboldt-Universität zu Berlin Institut für Informatik Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin Time: Monday, November 26th - 14:15 h Lecture: Marcin Pilipczuk (University of Warsaw) Title: The square root phenomenon:
subexponential algorithms in sparse graph classes While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches. Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading] Time: Monday, November 26th - 16:00 h Colloquium: Sebastian Siebertz (Humboldt-Universität zu
Berlin) Title: First-order interpretations of sparse graph classes Abstract: |