Elsevier Editorial System(tm) for Theoretical Computer Science Title: a 3.4713-approximation Algorithm for the Capacitated Multicast Tree Routing Problem a 3.4713-approximation Algorithm for the Capacitated Multicast Tree Routing Problem
Elsevier Editorial System(tm) for Theoretical Computer Science Title: a 3.4713-approximation Algorithm for the Capacitated Multicast Tree Routing Problem a 3.4713-approximation Algorithm for the Capacitated Multicast Tree Routing Problem
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Guohui Lin;Zhipeng Cai;Zhi-Zhong Chen
中科院分区：
文献类型：
--
作者：
Guohui Lin;Zhipeng Cai;Zhi-Zhong Chen
给定一个表示为边权图G=(V，E)的底层通信网络，源节点S∈V，目的节点集合D⊆V，容量k为正整数，在每个路由树中至多允许k个目的节点接收数据副本的约束下，容量受限多播树路由问题要求源S向所有目的节点发送数据的最小代价路由方案。路由方案的成本是其中所有单独路由树的成本之和。对已有的近似算法进行了改进，提出了一种新的算法，其最坏情况下的性能比为
Given an underlying communication network represented as an edge-weight graph G = (V, E), a source node s ∈ V , a set of destination nodes D ⊆ V , and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of