A polynomial time approximation scheme for embedding a directed hypergraph on a ring |
| |
| Authors: | Kang Li |
| |
| Affiliation: | a School of Information Science and Engineering, Shandong University, Jinan, Shandong Province, P.R. China
b Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong |
| |
| Abstract: | We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirect version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. |
| |
| Keywords: | Approximation algorithms Directed hyperedges embedding Rings |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
