TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 02.11.2012

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Partitioning Networks into Highly Connected Clusters with Maximum Edge Coverage

Dr. Falk Hüffner (TU Berlin)

Removing as few edges as possible from a graph such that the resulting graph consists of highly connected components is a natural problem in graph-based data clustering. Building on work by Hartuv and Shamir [Inf. Proc. Lett. 2000], we introduce the corresponding combinatorial optimization problem Highly Connected Deletion, show it to be NP-hard even on 4-regular graphs, provide fixed-parameter tractability results, and describe ILP models for the problem. We demonstrate that these exact solution methods (employing data reduction techniques as well as ILP solving) provide biologically meaningful results, being able to solve real-world PPI networks with up to 5 000 vertices and 12 000 edges. Compared to the method by Hartuv and Shamir, our exact approaches find more biologically interesting structures; Hartuv and Shamir's algorithm combined with our data reduction provides a good compromise between running time and solution quality.

Date
Speaker
Location
Language
02.11.2012 14:15
Falk Hüffner
TEL 512
english/german

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe