direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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