Abstract

The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion (the maximum number of paths that use any single link in the cycle) is minimized. This problem has many applications, including minimizing communication congestions in computer networks and parallel computations. The MCHEC problem is NP-hard. We give a 1.8-approximation algorithm for the problem. This improves the previous 2-approximation results. The algorithm has the optimal O(mn) time for the hypergraph with m hyperedges and n nodes.


Original document

The different versions of the original document can be found in:

http://dx.doi.org/10.1007/978-3-540-24596-4_10
https://dblp.uni-trier.de/db/conf/hipc/hipc2003.html#GuW03,
https://link.springer.com/chapter/10.1007%2F978-3-540-24596-4_10,
https://core.ac.uk/display/24625584,
https://www.scipedia.com/public/Gu_Wang_2010a,
https://rd.springer.com/chapter/10.1007/978-3-540-24596-4_10,
https://academic.microsoft.com/#/detail/1545073706
Back to Top

Document information

Published on 01/01/2010

Volume 2010, 2010
DOI: 10.1007/978-3-540-24596-4_10
Licence: CC BY-NC-SA license

Document Score

0

Views 1
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?