10 marca 2015 10:15
[Seminarium ZOK]. Jakub Łącki: Dynamic Steiner Tree
Wtorek, 10:15-12:00, sala 310.
Abstract. We study the Steiner tree problem over a dynamic set of terminals. 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 in G which is a good approximation of the minimum Steiner tree spanning a terminal set S ⊆ V, which changes over time. The changes applied to the terminal set are either terminal additions or removals. 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 possible.
We show that we can maintain an 12+epsilon approximate Steiner tree, in O(n^{1/2} * polylog(n)) time per terminal insertion or deletion. In the case of planar graphs we obtain a faster algorithm, whose approximation ratio is 4+epsilon and the update time is polylogarithmic.
This is joint work with Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski and Anna Zych.