Effective and Efficient Data Reduction for the Subset Interconnection Design Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F13%3A00209351" target="_blank" >RIV/68407700:21240/13:00209351 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-45030-3_34" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-45030-3_34</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-45030-3_34" target="_blank" >10.1007/978-3-642-45030-3_34</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Effective and Efficient Data Reduction for the Subset Interconnection Design Problem

Popis výsledku v původním jazyce

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 V1, V2, . . . ,Vm, and asks for a minimum-cardinality edge set Esuch that for the graph G = (V,E) all induced subgraphs G[V1],G[V2], . . . , G[Vm] 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? p

Název v anglickém jazyce

Effective and Efficient Data Reduction for the Subset Interconnection Design Problem

Popis výsledku anglicky

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 V1, V2, . . . ,Vm, and asks for a minimum-cardinality edge set Esuch that for the graph G = (V,E) all induced subgraphs G[V1],G[V2], . . . , G[Vm] 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? p

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISBN

978-3-642-45029-7

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

11

Strana od-do

361-371

Název nakladatele

Springer Science+Business Media

Místo vydání

Berlin

Místo konání akce

Hong Kong

Datum konání akce

16. 12. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—