論文

査読有り
2007年5月

Approximation algorithms for multicast routings in a network with multi-sources

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
  • Ehab Mosry
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
DOI
https://doi.org/10.1093/ietfec/e90-a.5.900
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902229777592008
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000246818700004&DestApp=WOS_CPL
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

エクスポート
BibTeX RIS