Algorithms and Implementation for Interconnection Graph Problem
Algorithms and Implementation for Interconnection Graph Problem
复制标题
互连图问题的算法与实现
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Jason B. Ernst
中科院分区：
文献类型：
--
作者：
Hongbing Fan;Christian Rosenke;Yu;Jason B. Ernst
互连图问题（IGP）是为给定的HyperGraph H =（v，r）A Graph G =（v，e）计算，边缘数量最小| E |如此适合所有Hyperedges n？ r连接的NIS的指标子图。计算可行的互连图基本上是由可重构互连网络设计的。本文证明，即使在最多三个顶点的Hhave的所有超蛋中，IGP也是NP完整的，并且很难近似。之后，它提出了一种基于搜索树的参数化算法，表明当他的有限的高度尺寸时，该问题是固定参数的。此外，该论文提供了基于还原的贪婪算法，并以其实验依据结束。
The Interconnection Graph Problem (IGP) is to compute for a given hypergraph H= (V, R) a graph G= (V, E) with the minimum number of edges |E| such that for all hyperedges N? Rthe subgraph of Ginduced by Nis connected. Computing feasible interconnection graphs is basically motivated by the design of reconfigurable interconnection networks. This paper proves that IGP is NP-complete and hard to approximate even when all hyperedges of Hhave at most three vertices. Afterwards it presents a search tree based parameterized algorithm showing that the problem is fixed-parameter tractable when the hyperedge size of His bounded. Moreover, the paper gives a reduction based greedy algorithm and closes with its experimental justification.