Title :
A 2-Approximation Algorithm for Weighted Directed Hypergraph Embedding in a cycle
Author :
Wang, Qi ; Zhao, Xiuheng ; Zheng, Xiaowei ; Liu, Xiaoshan
Author_Institution :
Hebei Univ. of Econ. & Bus., Shijiazhuang
Abstract :
The problem of weighted directed hypergraph embedding in a cycle (denoted by WDHEC for short) is to embed the weighted directed hyperedges of a hypergraph as the weighted directed paths around a cycle such that maximal congestion-the sum of weight of the paths that use any physical link in the cycle-is minimized. In this paper we show that the WDHEC problem is NP-complete even when each hyperedge contains exactly two vertices. A linear-time algorithm with performance ratio two is presented by a greedy algorithm.
Keywords :
computational complexity; directed graphs; greedy algorithms; minimisation; NP-complete problem; approximation algorithm; greedy algorithm; linear-time algorithm; maximal congestion minimization problem; weighted directed hypergraph cycle embedding; Application software; Approximation algorithms; Computer networks; Concurrent computing; Embedded computing; Greedy algorithms; Multicast communication; Physics computing; Polynomials; Routing; embedding; hypergraph; integer linear programming;
Conference_Titel :
Natural Computation, 2008. ICNC '08. Fourth International Conference on
Conference_Location :
Jinan
Print_ISBN :
978-0-7695-3304-9
DOI :
10.1109/ICNC.2008.241
