TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 30.01.2014

isti-logo

Page Content

to Navigation

Algorithm Engineering für das Auffinden dichter Teilgraphen in dünnen Graphen

Kolja Stahl (TU Berlin)

Thema des Vortrags ist das mu-Cliquen Problem, welches darin besteht, zu entscheiden, ob ein Teilgraph mit k Knoten und Dichte mindestens mu existiert. Dieses Problem hat zahlreiche Anwendungen in der Bioinformatik und im Data Mining. Viele der dort vorkommenden Graphen sind sehr dünn (z.B. Protein-Protein Netzwerke mit Dichte < 0.003). Das Finden dichter verbundener Teilgraphen dient hier unter anderem der Identifikation funktionaler Gruppen.
Es wird ein Algorithmus zum Lösen des Entscheidungsproblems vorgestellt (basierend auf der Arbeit von Komusiewicz und Sorge [IPEC'12]), dessen Laufzeitanteil nur vom Maximalgrad abhängt. Hauptaugenmerk liegt hierbei auf der Implementierung, Optimierung und Parallelisierung. Weiterhin wird mit der Quasi-Vererbbarkeit eine weitere interessante Eigenschaft von mu-Cliquen vorgestellt.

Date
Speaker
Location
Language
30.01.2014 16:15
Kolja Stahl
TEL 512
deutsch

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe