Title :
Minimum-Congestion Weighted Hypergraph Embedding in a Rings Cycle
Author :
Wang, Qi ; Liu, Xiaoshan ; Zheng, Xiaowei ; Li, Chunlin
Author_Institution :
Hebei Univ. of Econ. & Bus., Shijiazhuang, China
fDate :
March 31 2009-April 2 2009
Abstract :
A rings cycle is an undirected graph obtained from a cycle by replacing each edge of the cycle with a ring so that two rings corresponding to the two end-nodes of any edge have precisely one node in common. Given a weighted hypergraph on a rings cycle, Minimum-Congestion Weighted Hypergraph Embedding in a Rings Cycle (WHERC) is to embed each weighted hyperedges as a path in the rings cycle such that maximal congestion-the sum of weight of embedding paths that use any edge in the rings cycle-is minimized.We prove that the WHERC problem is NP-complete. 2-approximation algorithms are presented for the WHERC problem and a related problem-WDHETR.
Keywords :
approximation theory; computational complexity; directed graphs; NP-complete; approximation algorithms; minimum-congestion weighted hypergraph; rings cycle; undirected graph; weighted hyperedges; Application software; Approximation algorithms; Business communication; Computer networks; Computer science; Concurrent computing; Electronic design automation and methodology; Multicast communication; Polynomials; Routing; embedding; hypergraph; integer linear programming(ILP); polynomial-time approximation scheme (PTAS);
Conference_Titel :
Computer Science and Information Engineering, 2009 WRI World Congress on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-0-7695-3507-4
DOI :
10.1109/CSIE.2009.57
