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.
| Original language | English |
|---|---|
| Pages (from-to) | 319-328 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 24 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Oct 2012 |
| Externally published | Yes |
Research Keywords
- Directed hypergraph
- Embedding
- PTAS
Fingerprint
Dive into the research topics of 'A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver