direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Network-based Clustering under Heterogeneity Constraints

Sharon Bruckner (FU Berlin)

In this talk I present work done by Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Sven Thiel, and Johannes Uhlmann and myself on the the Colorful Components problem.
Given a vertex-colored graph, we want to delete a minimum number of edges such that no connected component contains two vertices of the same color. This problem has applications in many fields such as biology (multiple sequence alignment, network alignment) and data mining (the wikipedia language graph). We show that Colorful Components is polynomial-time solvable for two colors, but NP-hard already for three colors or on binary trees. On the positive side, we give a fixed-parameter algorithm for trees with running time 2^{c}n^{O(1)}, where c is the number of colors and n is the number of vertices in the tree. For general graphs G, we give a fixed-parameter algorithm with running time O((c-1)^k|G|), where k is the number of edges to delete. As additional solving strategies, we present polynomial-time data reduction rules, an ILP formulation, and a formulation as implicit hitting set problem. We present experiments with real-world data, compare the solution methods above and discuss our results and future plans.

date
speaker
location
language
19.01.2012 16:15
Sharon Bruckner
FR 6510
english

Back to the research colloquium site.

Zusatzinformationen / Extras