【摘要】 H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的映射树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优映射使得G中任一边被H所有超边的映射经过的最大次数最小.应用超图嵌入圈(MCHEC)问题的算法可得超图嵌入树环问题的一个2-近似算法.更多还原

【Abstract】 Given a hypergraph H on a trees of rings G,Embedding Hypergraph in a Trees of Rings(EHTR)is to embed each hyperedge of H as a tree in G such that the maximal times that all these trees using any single edge of G is minimal.This problem is initiated from Minimum-Congestion Hypergraph Embedding in a Cyle(MCHEC).By applying above method a 2-approximation algorithm of the WDHETR problem can be obtained.更多还原