کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225737 | 1701207 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved algorithm for diameter-optimally augmenting paths in a metric space
ترجمه فارسی عنوان
یک الگوریتم بهبود یافته برای مسیرهای مطلوب افزایش قطر در یک فضای متریک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
قطر، نمودارهای مسیر، مسیرهای افزایشی، قطر کم فضای متریک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O(nlog3â¡n) time. In this paper, based on new observations and different algorithmic techniques, we present an O(nlogâ¡n) time algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 75, December 2018, Pages 11-21
Journal: Computational Geometry - Volume 75, December 2018, Pages 11-21
نویسندگان
Haitao Wang,