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 € R the subgraph of G induced by N is 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 H have at most three vertices. Afterwards it presents a search tree based parameterized algorithm showing that the problem is fixed-parameter tractable when the hyper-edge size of H is bounded. Moreover, the paper gives a reduction based greedy algorithm and closes with its experimental justification.
展开▼
机译：互连图问题（IGP）将为给定超图H =（V，R）计算图G =（V，E），且边的数量最少| E |。这样，对于所有超边N€R，由N诱导的G的子图都是相连的。计算可行的互连图基本上是由可重配置互连网络的设计驱动的。本文证明，即使H的所有超边最多具有三个顶点，IGP也是NP完全的，并且难以近似。然后，它提出了一种基于搜索树的参数化算法，该算法表明，当H的超边缘尺寸有界时，该问题是固定参数可处理的。此外，本文给出了一种基于约简的贪婪算法，并以其实验依据作为结尾。
展开▼
