Efficient Algorithm for Embedding Hypergraphs in a Cycle

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.

Document type: Part of book or chapter of book

Full document

Original document

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

• http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf