On packing and coloring hyperedges in a cycle
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 2140-2151 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 155 |
Issue number | 16 |
Publication status | Published - 1 Oct 2007 |
Link(s)
Abstract
Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link ej on the cycle is used at most cj times, each hyperedge hi has its profit pi and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC). In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link ej has same capacity k, we propose an algorithm with approximation ratio frac(3, 2). © 2007 Elsevier B.V. All rights reserved.
Research Area(s)
- Approximation algorithm, Hyperedge, Path coloring
Citation Format(s)
On packing and coloring hyperedges in a cycle. / Li, Jianping; Wang, Lusheng; Zhao, Hao.
In: Discrete Applied Mathematics, Vol. 155, No. 16, 01.10.2007, p. 2140-2151.
In: Discrete Applied Mathematics, Vol. 155, No. 16, 01.10.2007, p. 2140-2151.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review