A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
复制标题
DOI：
10.1016/j.tcs.2011.08.014
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
Chaoxia Yang;Guojun Li
中科院分区：
文献类型：
--
作者：
Chaoxia Yang;Guojun Li
最小拥塞超图嵌入加权圈问题（MCHEWC）是将超图的超边作为路嵌入到一个加权圈中，使得最大拥塞最小。这个问题是NP难的。在本文中，我们提出了一个多项式时间近似计划（PTAS）的这个问题。
The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion is minimized. This problem is NP-hard. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem.