BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20151025T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20150329T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20160327T020000
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.7140.field_data.0@www.diag.uniroma1.it
DTSTAMP:20240615T120313Z
CREATED:20151016T140120Z
DESCRIPTION:We study the Steiner tree problem over a dynamic set of termina
ls. We consider the model where we are given an n-vertex graph G = (V\, E\
, w) with positive real edge weights\, and our goal is to maintain a tree
which is a good approximation of the minimum Steiner tree spanning a termi
nal set S (a subset of V)\, which changes over time. The changes applied t
o the terminal set are either terminal additions (incremental scenario)\,
terminal removals (decremental scenario)\, or both (fully dynamic scenario
). Our task here is twofold. We want to support updates in sublinear o(n)
time\, and keep the approximation factor of the algorithm as small as poss
ible.We show that we can maintain a (6 + epsilon)-approximate Steiner tree
of a general graph in roughly O(sqrt(n) log D) time per terminal addition
or removal. Here\, D denotes the stretch of the metric induced by G. For
planar graphs we achieve the same running time and the approximation ratio
of (2 + epsilon). Moreover\, we show faster algorithms for incremental an
d decremental scenarios. Finally\, we show that if we allow higher approxi
mation ratio\, even more efficient algorithms are possible. In particular
we show a polylogarithmic time (4 + epsilon)-approximate algorithm for pla
nar graphs. One of the main building blocks of our algorithms are dynamic
distance oracles for vertex-labeled graphs\, which are of independent inte
rest. We also improve and use the online algorithms for the Steiner tree p
roblem.
DTSTART;TZID=Europe/Paris:20151030T120000
DTEND;TZID=Europe/Paris:20151030T120000
LAST-MODIFIED:20151029T114054Z
LOCATION:Aula Magna DIAG\, via Ariosto 25
SUMMARY:Dynamic Steiner Tree - Jakub Lacki (Sapienza University of Rome)
URL;TYPE=URI:http://www.diag.uniroma1.it/node/7140
END:VEVENT
END:VCALENDAR