direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras