1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization) :

NDLデジタルコレクション 被引用文献1件
  • Morsy,Ehab
    Department of Applied Mathematics and Physics Graduate School of Informatics Kyoto University
  • Nagamochi,Hiroshi
    Department of Applied Mathematics and Physics Graduate School of Informatics Kyoto University

この論文をさがす

説明

Let G=(V, E) be a connected graph such that each edge e∈E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S⊆V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z_1, Z_2, …, Z_e} of the terminal set S and a set of subtrees T_1, T_2, …, T_e of G such that Z_i consists of at most k terminals and each T_i spans Z_i∪{s}. The objective is to minimize Σ^e_<i=1>w(T_i), where w(T_i) is defined to be the sum of weights of all edges in T_i. In this paper, we propose a (3/2+(4/3)ρ)-approximation algorithm to the CMTR, where ρ is the best achievable approximation ratio for the Steiner tree problem. Our approximation improves the previous best ratio for the case of S=V from 2.9 to 17/6≃2.83.

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ