Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
复制标题
子集互连设计问题的多项式时间数据缩减
DOI：
10.1137/140955057
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
und M. Weller
中科院分区：
文献类型：
--
作者：
J. Chen;C. Komusiewicz;R. Niedermeier;M. Sorge;O. Suchý;und M. Weller
NP-hardSubset互连设计问题，又称最小主题连接覆盖问题，是一个具有广泛应用前景的问题，包括可扩展覆盖网络和真空系统的设计。它有一个有限集和一个子集的集合作为输入，并要求一个最小基数边集，使得所有的图诱导子图是连通的。我们研究子集互连设计的多项式时间的数据简化规则，保持构建最优解的可能性的上下文中。 我们的贡献是三方面的：第一，我们显示了早期的多项式时间数据减少规则的不正确性。其次，我们表明线性时间可解性的情况下，一个常数的子集，这意味着固定参数的参数易处理性。第三，我们提供了一个固定参数的小子集大小和树状输出图的易处理性结果。为了实现我们的结果，我们详细说明多项式时间的数据减少规则，也可能是实际使用solvingSubset互连设计。
The NP-hardSubset Interconnection Designproblem, also known asMinimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite setand a collection of subsets, and asks for a minimum-cardinality edge setsuch that for the graphall induced subgraphsare connected. We studySubset Interconnection Designin the context of polynomial-time data reduction rules that preserve the possibility of constructing optimal solutions. Our contribution is threefold: First, we show the incorrectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant numberof subsets, implying fixed-parameter tractability for the parameter. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solvingSubset Interconnection Design.
登录
查看更多内容
DOI：
--
发表时间：
2008
期刊：
International Conference on Combinatorial Optimization and Applications
影响因子：
--
作者：
Hongbing Fan;Christian Rosenke;Yu;Jason B. Ernst
通讯作者：
Jason B. Ernst
影响因子：
0.8
作者：
D. Du;Zevi Miller
通讯作者：
Zevi Miller
关于四组的最小可行图
DOI：
--
发表时间：
1995
期刊：
影响因子：
--
作者：
Xuyinfeng;Fuxiaobing
通讯作者：
Fuxiaobing
DOI：
--
发表时间：
2008
期刊：
International Conference on Foundations of Computer Science
影响因子：
--
作者：
Hongbing Fan;Yu
通讯作者：
Yu
影响因子：
2.7
作者：
Korach, E;Stern, M
通讯作者：
Stern, M