2007年5月
Approximation algorithms for multicast routings in a network with multi-sources
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
- ,
- 巻
- E90A
- 号
- 5
- 開始ページ
- 900
- 終了ページ
- 906
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietfec/e90-a.5.900
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G = (V,E) with a vertex set V, an edge set E and an edge weight w(e) >= 0, e epsilon E. We are given a source set S epsilon V with a weight g(e) >= 0, e epsilon S, a terminal set M subset of V - S with a demand function q : M -> R+, and a real number K > 0, where g(s) means the cost for opening a vertex s is an element of S as a source in a multicast tree. Then the CMMTR asks to find a subset S' subset of S, a partition {Z(1), Z(2),..., Z(l)) of M, and a set of subtrees T-1, T-2,..., T-l of G such that, for each i, Sigma(l is an element of Zi) q(t) <= K and T-i spans Z(i) boolean OR {s} for some s epsilon S'. The objective is to minimize the sum of the opening cost of S' and the constructing cost of (T-i), i.e., Sigma(s epsilon S') g(s) + Sigma(l)(i)=1 w(T-i), where w(T-i) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2puFL + PST)-approximation algorithm to the CMMTR, where puFL and PST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)rho(UFL) + (4/3)rho(ST)) -approximation algorithm.
- リンク情報
- ID情報
-
- DOI : 10.1093/ietfec/e90-a.5.900
- ISSN : 0916-8508
- eISSN : 1745-1337
- J-Global ID : 200902229777592008
- Web of Science ID : WOS:000246818700004