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

Volume

6

fYear

2008

fDate

18-20 Oct. 2008

Firstpage

377

Lastpage

381

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Natural Computation, 2008. ICNC '08. Fourth International Conference on

Conference_Location

Jinan

Print_ISBN

978-0-7695-3304-9

Type

conf

DOI

10.1109/ICNC.2008.241

Filename

4667863