.png){kind=icon}
返回
Efficient algorithms for minimum congestion hypergraph embedding in a cycle
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2006.34.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 hyperedges of a hypergraph as paths in a cycle with the same node set such that the maximum congestion (the maximum number of paths that use any single edge in the cycle) is minimized. The MCHEC problem has many applications, including optimizing communication congestions in computer networks and parallel computing. The problem is NP-hard. In this paper, we give a 1.8-approximation algorithm for the MCHEC problem. This improves the previous 2-approximation results. Our algorithm has the optimal time complexity O(mn) for a hypergraph with m hyperedges and n nodes. We also propose an algorithm which finds an embedding with the optimal congestion L* for the MCHEC problem in O(n(nL*)(L*)) time. This improves the previous O((mn)(L*+1)) time algorithm.
Keyword:
hypergraph embedding
approximation algorithms
communication on rings
edge congestion minimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
暂无机构信息
引用论文
.png){kind=icon}
TGA-DTA, infrared and x-ray powder diffraction studies on strontium nitroprusside and its hydrates
PREAI
分享收藏Effects of composition and processing on properties of modified maghemite for high-density recording
PREAI
分享收藏分享收藏
查看更多内容