کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414747 | 681020 | 2014 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An optimal algorithm for the Euclidean bottleneck full Steiner tree problem
ترجمه فارسی عنوان
یک الگوریتم بهینه برای مشکل تضعیف استیینر تنگنائی اقلیدسی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداقل درخت درختی درخت استینر، طول تقریبی، گراف یو
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P and S be two disjoint sets of n and m points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to S, in which each point of P is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in O((n+m)logm) time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part A, April 2014, Pages 377–380
Journal: Computational Geometry - Volume 47, Issue 3, Part A, April 2014, Pages 377–380
نویسندگان
Ahmad Biniaz, Anil Maheshwari, Michiel Smid,