点击次数：

所属单位：山东大学数学学院

发表刊物：ACM Transactions on Algorithms

摘要：We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.

The minimum congestion hypergraph embedding in a cycle problem is known to be NP-hard and its graph version, the minimum congestion graph embedding in a cycle, is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been ...

全部作者：Deng. X.

第一作者：Li, G.

论文类型：期刊论文

学科门类：理学

一级学科：数学

文献类型：J

卷号：412

期号：48

是否译文：否

发表时间：2009-03-01

收录刊物：SCI