direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Effective and Efficient Data Reduction for the Subset Interconnection Design Problem

Dipl.-Inf. Manuel Sorge (TU Berlin)

The NP-hard Subset Interconnection Design problem is motivated by applications in designing vacuum systems and scalable overlay networks. It has as input a set V and a collection of subsets V_1, V_2, ..., V_m, and asks for a minimum-cardinality edge set E such that for the graph G = (V, E) all induced subgraphs G[V_1], G[V_2 ], ..., G[V_m] are connected. It has also been studied under the name Minimum Topic-Connected Overlay. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve optimality. Our contribution is threefold: First, we point out flaws in earlier polynomial-time data reduction rules. Second, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. Third, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. To achieve our results, we elaborate on polynomial-time data reduction rules (partly "repairing" previous flawed ones) which also may be of practical use in solving Subset Interconnection Design.

05.12.2013 16:15
Manuel Sorge
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras