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.ugovricerca.uniroma1.it
DTSTAMP:20260407T200033Z
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.ugovricerca.uniroma1.it/node/7140
END:VEVENT
END:VCALENDAR