Institution:山东大学数学学院

Title of Paper:A Polynomial-Time Approximation Scheme for Embedding Hypergraph in a Cycle

Journal:ACM Transactions on Algorithms

Summary: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 ...

First Author:Li, G.

All the Authors:Deng. X.

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

Included Journals:SCI

Release Time:2019-07-10