BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Given n ball-like objects in some metric space\, one can defin
 e a geometric intersection graph where the vertices correspond to objects\,
  and edges are added for pairs of objects with a non-empty intersection. A 
 separator of a graph is a small or otherwise "nice" vertex set whose remova
 l disconnects the graph into two roughly equal parts. In this talk\, we wil
 l see some separator theorems for intersection graphs in Euclidean and hype
 rbolic space. One can use these separators to design simple divide and conq
 uer algorithms for several classical NP-hard problems. It turns out that we
 ll-designed separators often lead to subexponential algorithms with optimal
  running times (up to constant factors in the exponent) under the Exponenti
 al Time Hypothesis (ETH). 
DTSTAMP:20200122T151100
DTSTART:20200203T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Sándor Kisfaludi-Bak (Max Planck Institut Saarbrücken): Separators 
 and exact algorithms for geometric intersection graphs
UID:95692990@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20200203-C-Kis
 faludi.html
END:VEVENT
END:VCALENDAR