کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430574 688045 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the approximability of Dense Steiner Problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the approximability of Dense Steiner Problems
چکیده انگلیسی

We study the approximation complexity of the ϵ-Dense Steiner Tree Problem which was introduced by Karpinski and Zelikovsky (1998) [13]. They proved that for each ϵ>0ϵ>0, this problem admits a PTAS. Based on their method we consider here dense versions of various Steiner Tree problems. In particular, we give polynomial time approximation schemes for the ϵ-Dense k-Steiner Tree Problem, the ϵ-Dense Prize Collecting Steiner Tree Problem and the ϵ-Dense Group Steiner Tree Problem. We also show that the ϵ  -Dense Steiner Forest Problem is approximable within ratio 1+O((∑ilog|Si|)/(∑i|Si|))1+O((∑ilog|Si|)/(∑i|Si|)) where S1,…,SnS1,…,Sn are the terminal sets of the given instance. This ratio becomes small when the number of terminal sets is small compared to the total number of terminals.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 21, July 2013, Pages 41–51
نویسندگان
,