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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200203-C-Kisfaludi.html
END:VEVENT
END:VCALENDAR