A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 319-328 |
| Journal / Publication | Journal of Combinatorial Optimization |
| Volume | 24 |
| Issue number | 3 |
| Publication status | Published - Oct 2012 |
| Externally published | Yes |
Link(s)
Abstract
Given a directed hypergraph H = (V ,E H ), we consider the problem of embedding all directed hyperedges on a weighted ring. The objective is to minimize the maximum congestion which is equal to the maximum product of the weight of a link and the number of times that the link is passed by the embedding. In this paper, we design a polynomial time approximation scheme for this problem. © Springer Science+Business Media, LLC 2011.
Research Area(s)
- Directed hypergraph, Embedding, PTAS
Citation Format(s)
A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring. / Li, Jianping; Li, Weidong; Wang, Lusheng.
In: Journal of Combinatorial Optimization, Vol. 24, No. 3, 10.2012, p. 319-328.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
