| 一个超图嵌入问题的多项式时间近似算法 |
| |
| 引用本文： | 王骁力.一个超图嵌入问题的多项式时间近似算法[J].南阳师范学院学报,2008,7(12). |
| |
| 作者姓名： | 王骁力 |
| |
| 作者单位： | 南阳师范学院数学与统计学院,河南,南阳,473061 |
| |
| 基金项目： | 南阳师范学院高层次人才资助项目
|
| |
| 摘 要： | 把定义在一个圈上的超图的每个超边映射为这个圈的一条路,每条超边的顶点均在对应的映射中,要求使圈中的任一边经过的路的最大次数最小,称此问题为超图在圈中的最小嵌入问题.将此问题归结为最近串选取问题,从而证明该问题存在多项式时间近似算法.
|
| 关 键 词： | 超图在圈中嵌入 最小边阻塞度 最近串选取问题 多项式时间近似算法 |
Approximation algorithm about hypergraph embedding in a cycle |
| |
| WANG Xiao-li.Approximation algorithm about hypergraph embedding in a cycle[J].Journal of Nanyang Teachers College,2008,7(12). |
| |
| Authors: | WANG Xiao-li |
| |
| Abstract: | The problems of Minimum Congestion Hypergraph Embedding in a Cycle(MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion(the maximum number of paths that use any single link in a cycle) is minimized.The MCHEC problem is NP-hard.In this paper,we consider the equivalent of this problem with another important problem in computational biology,and get conclusion that MCHEC has a PTAS. |
| |
| Keywords: | hypergraph embedding in a cycle link congestion minimization closest string selection problem PTAS |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
