树环中的流量疏导问题研究  

Congestion Division Problems in Net of Trees of Rings

作　　者：王琦[1] 姚立[1] 徐彩云 

机构地区：[1]河北经贸大学数学与统计学学院,河北石家庄050061 [2]罗塞洛(温州)明胶有限公司,浙江温州325411

出　　处：《数学的实践与认识》2012年第12期266-270,共5页Mathematics in Practice and Theory

基　　金：2011年度河北省自然基金(A2011207003);光网络中流量疏导问题的研究与应用;2011年度河北省高校科学研究优秀青年基金(Y2011115);网络中超图嵌入问题的研究应用

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

关 键 词：树环 PTAS 嵌入 

分 类 号：O157.5[理学—数学]