.png){kind=icon}
返回
Minimum-congestion hypergraph embedding in a cycle
.png){kind=icon}
PRE
AI
DOI：10.1109/12.589233.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The minimum-congestion hypergraph embedding in a cycle (MCHEC) problem is to embed the n edges in an m-vertex hypergraph as paths in a cycle on the same number of vertices, such that congestion--the maximum number of paths that use any single edge in the cycle--is minimized. The MCHEC problem has applications in electronic design automation and parallel computing. In this paper, it is proven that the MCHEC problem is NP-complete. An O((nm)(k+1)) algorithm is described that computes an embedding with congestion k or determines that such an embedding does not exist. Finally, a linear-time approximation algorithm for arbitrary instances is presented that computes an embedding whose congestion is at most three times optimal.
Keyword:
hypergraph embedding in a cycle
congestion
NP-completeness
approximation algorithms
routing around a rectangle
moat routing
ring routing
期刊
IF:
3.8
论文数:
5.4K
被引数:
9.8K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏分享收藏
没有更多内容
没有更多内容