2-Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle Rings

摘要

A cycle rings is an undirected graph obtained from a cycle by replacing each edge of the cycle with a ring so that two rings corresponding to the two end-nodes of any edge have precisely one node in common. Given a weighted hyper graph on a cycle rings, Minimum-Congestion Weighted Hyper graph Embedding in a cycle rings (WHECR) is to embed each weighted hyperedges as a path in the cycle rings such that maximal congestion-the sum of weight of embedding paths that use any edge in the cycle rings -is minimized. We prove that the WHECR problem is NP-complete. 2-approximation algorithms are presented for the WHECR problem.