Affiliation of Author(s):山东大学数学学院

Journal:ACM Transactions on Algorithms

Abstract:We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.

The minimum congestion hypergraph embedding in a cycle problem is known to be NP-hard and its graph version, the minimum congestion graph embedding in a cycle, is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been ...

All the Authors:Deng. X.

First Author:Li, G.

Indexed by:Journal paper

Discipline:Natural Science

First-Level Discipline:Mathematics

Document Type:J

Volume:412

Issue:48

Translation or Not:no

Date of Publication:2009-03-01

Included Journals:SCI