Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2011/12 / Oberseminar / Sabrina Schewtschenko, Undirected Graph Connectivity (USTCON) in Logspace


Inhaltsbereich

Sabrina Schewtschenko, Undirected Graph Connectivity (USTCON) in Logspace

TCS Oberseminar, Montag (!), 27.02.2012, 14:15 Uhr
Wann 14:15 15:15 27.02.2012
von bis
Wo L109
Termin übernehmen vCal
iCal

Sabrina Schewtschenko
Undirected Graph Connectivity (USTCON) in Logspace

In 2005 Omer Reingold proved that the USTCON (Undirected st-connectivity) is solvable in log-space and thus the classes SL and L are the same. Reingold introduced the new technique 'rotation map' to represent graphs in a handsome way and thus was able to state an algorithm which solves the USTCON problem in expander graphs in log-space. Now we are confronted to build up out of a given arbitrary graph an expander graph. To come up with this task we use the techniques 'powering' of a graph and the Reingold's 'zig-zag-product'. The required proves are given by linear algebra, due to the fact that we can represent graphs always by their associated matrix.

Artikelaktionen

abgelegt unter:

Funktionsleiste