DocumentCode
525180
Title
A PTAS for embedding a directed hypergraphin a tree of rings
Author
Yang, Chaoxia ; Li, Guojun
Author_Institution
Dept. of Math., Shandong Univ., Jinan, China
Volume
1
fYear
2010
fDate
25-27 June 2010
Abstract
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.
Keywords
approximation theory; computational complexity; directed graphs; trees (mathematics); NP-complete; PTAS; directed hypergraphin; polynomial time approximation scheme; tree of rings; Approximation algorithms; Biochemistry; Biology computing; Chaotic communication; Embedded computing; Mathematics; Polynomials; Tree graphs; Virtual reality; approximation algorithm; directed hypergraph; embedding; tree of rings;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Design and Applications (ICCDA), 2010 International Conference on
Conference_Location
Qinhuangdao
Print_ISBN
978-1-4244-7164-5
Electronic_ISBN
978-1-4244-7164-5
Type
conf
DOI
10.1109/ICCDA.2010.5540746
Filename
5540746
Link To Document