摘要
把定义在一个圈上的超图的每个超边映射为这个圈的一条路,每条超边的顶点均在对应的映射中,要求使圈中的任一边经过的路的最大次数最小,称此问题为超图在圈中的最小嵌入问题.将此问题归结为最近串选取问题,从而证明该问题存在多项式时间近似算法.
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.
出处
《南阳师范学院学报》
CAS
2008年第12期1-3,共3页
Journal of Nanyang Normal University
基金
南阳师范学院高层次人才资助项目(nytc026)