On March 3, 2015, Prof. Harald Räcke from the Technische Universität München will give a talk about "Fast Tree Approximations of Graphs" in the context of the SFB 901 colloquium.
Abstract:
Given a graph G=(V,E,c) with edge capacities, a cut-sparsifier for G is a graph H=(V',E',c') with V\subseteq V' that approximates the mincuts of G in the following sense. Given any bipartition U,V-U of the vertex set of G the mincut separating U and V-U is approximately (up to a factor of q) the same in G as in H.
This talk focuses on the construction of a sparsifier H for a given undirected graph G that not only obtains a good quality but has the additional property that H is a tree. Such tree approximations of graphs play an important role in the design of oblivious routing strategies and also form the basis for approximation and online algorithms for various cut problems in graphs. We give the first algorithm for constructing such a sparsifier that obtains close to linear running.