A PTAS for embedding a directed hypergraphin a tree of rings
Chaoxia Yang, Guojun Li · 2010
We study the problem of embedding a directed hypergraph in a tree of rings which has applications in optimal network communication. Such problems are NP-complete, therefore we are interested in searching for an approximate solution (to arbitrary accuracy) within polynomial time. In this paper, we present a polynomial time approximation scheme (PTAS) for the problem of directed hypergraph embedding in a tree of rings.