Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

CRC 901 – On-The-Fly Computing (OTF Computing) Show image information

CRC 901 – On-The-Fly Computing (OTF Computing)

Tuesday, 03.03.2015 | 14.00 Uhr | Fürstenallee 11, Lecture Hall F1.110

Talk given by Prof. Harald Räcke, Technische Universität München (TUM)

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.


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.

The University for the Information Society