کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435527 689912 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Size-constrained tree partitioning: Approximating the multicast k-tree routing problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Size-constrained tree partitioning: Approximating the multicast k-tree routing problem
چکیده انگلیسی

In the multicast k-tree routing problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting. Several approximation algorithms, with increasing performance, have been proposed in the last several years; the most recent ones rely heavily on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line. The algorithm has a worst-case performance ratio of , where ρ denotes the best approximation ratio for the Steiner minimum tree problem. The proofs of the technical routing lemmas also provide some insights into why such a performance ratio could be the best possible that one can get using this tree partitioning technique.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 3, 21 January 2011, Pages 240-245