+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************
Zeit: Donnerstag, 6. Oktober 2022, 15:00 Uhr Ort: Raum 9222, Ahornstr. 55
Referent: Tim Hartmann M.Sc. Lehrstuhl Informatik 1
Thema: Facility Location on Graphs
Abstract:
We study two closely related Facility Location problems on graphs where all edges have unit length and where the facilities may also be positioned in the interior of the edges. For delta-Dispersion the goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. For delta-Covering the goal is to cover the entire graph with the minimum number of facilities; that is, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most delta from one of these facilities.
We investigate the algorithmic complexity of these problems for every real distance value delta. Further, we explore the complexity of these problems with the solution size as parameter. Finally, we study delta-Dispersion with parameters that measure the complexity of the input graph, such as treewidth, treedepth and neighborhood diversity.
Es laden ein: die Dozentinnen und Dozenten der Informatik