超图嵌入图的最小拥挤问题展望
李国君
摘要：We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion,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 approxima-tion scheme for the weighted version is known. For the hypergraphmodel, several approximation algorithms with a ratio of two have been previously published. A recent works on this problem reduced the approximation ratio to 1.5. We present a polynomial time approximation scheme in this paper,settling the debate regarding if the problem is polynomial time approximable
机标关键词：图嵌入polynomial timeapproximation algorithmsapproximation ratioGraph Embedding
分类号：O157.6(代数、数论、组合理论)
论文发表日期：2008-01-01
在线出版日期：2026-08-28（本平台首次上网日期，不代表文献的发表时间）
页数：9( 19-27 )
英文信息