کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777195 1632576 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Shared Broadcast Tree Problem and MST
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Shared Broadcast Tree Problem and MST
چکیده انگلیسی

The shared broadcast tree (SBT) problem in Euclidean graphs resembles the minimum spanning tree (MST) problem, but differs from MST in the definition of the objective function. The SBT problem is known to be NP-hard. In the current work, we analyse how closely the MST-solution approximates the SBT-solution, and we prove in particular that the approximation ratio is at least 6. Further, we conduct numerical experiments comparing the MST-solution and the optimum. The results show that the cost of the MST-solution is around 20% higher than the optimal cost.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 5-8
نویسندگان
,