.png){kind=icon}
Return
Minimum-congestion hypergraph embedding in a cycle
.png){kind=icon}
PRE
AI
DOI：10.1109/12.589233.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
hypergraph embedding in a cycle
congestion
NP-completeness
approximation algorithms
routing around a rectangle
moat routing
ring routing
Journal
IF:
3.8
Papers:
5.4K
Citations:
9.8K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
no more
no more