Improved Approzimation Algorithms for the Capacitated Multicast Routing Problem
Two models for the Capacitated Multicast Routing Problem are considered, which are the Multicast kPath Routing and the Multicast k-Tree Routing. Under these models, two improved approximation algorithms are presented, which have worst case performance ratios of 3 and (2+p), respectively. Here p denotes the best approximation ratio for the Steiner MinimuM Tree problem, and it is about 1.55 at the writing of the paper. The two approximation algorithms improve upon the previous best ones having performance ratios of 4 and (2.4 + p), respectively. The designing techniques developed in the paper could be applicable to other similar networking problems.
Capacitated Multicast Routing Approzimation Algorithm Steiner Minimum Tree Tree Partitioning
Zhipeng Cai Guohui Lin Guoliang Xue
Department of Computing Science, University of Alberta Edmonton, Alberta T6G 2E8, Canada Department of Computer Science and Engineering, Arizona State University Tempe, Arizona 85287-5406,
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
136-145
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）