| 超图在圈中的嵌入问题 |
| |
| 引用本文： | 王琦,刘晓姗.超图在圈中的嵌入问题[J].数学的实践与认识,2011,41(13). |
| |
| 作者姓名： | 王琦 刘晓姗 |
| |
| 作者单位： | 1. 河北经贸大学数学与统计学院,河北石家庄,050061
2. 石家庄经济学院理学院,河北石家庄,050031 |
| |
| 基金项目： | 2011年度河北省自然科学基金(A2011207003) |
| |
| 摘 要： | H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.
|
| 关 键 词： | 嵌入 超图 PTAS |
Embedding Hypergraph In a Cycle |
| |
| WANG Qi,LIU Xiao-shan.Embedding Hypergraph In a Cycle[J].Mathematics in Practice and Theory,2011,41(13). |
| |
| Authors: | WANG Qi LIU Xiao-shan |
| |
| Institution: | WANG Qi~1,LIU Xiao-shan~2 (1.School of Mathematics & Statistic,Hebei University of Economics & Business,Hebei 050061,China) (2.School of Math & Physics,Shijiazhuang University of Economics,Shijiazhuang 050031,China) |
| |
| Abstract: | Given a hypergraph H on a cycle G,the problem Minimum-Congestion Hypergraph Embedding in a Cyle(MCHEC)is to embed each hyperedge of H as a path in G such that maximal times that these paths using any edge of G is minimal.The MCHEC problem can be solved as a PTAS by the method of combinatorial optimization and probability. |
| |
| Keywords: | embedding hypergraph PTAS |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
