کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414276 | 680874 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Shortest paths in intersection graphs of unit disks
ترجمه فارسی عنوان
کوتاهترین مسیرها در نمودارهای تقاطع دیسکهای واحد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوتاهترین مسیر، نمودار تقاطع، گراف دیسک واحد، نمودار هندسی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G be a unit disk graph in the plane defined by n disks whose positions are known. For the case when G is unweighted, we give a simple algorithm to compute a shortest path tree from a given source in O(nlogn)O(nlogn) time. For the case when G is weighted, we show that a shortest path tree from a given source can be computed in O(n1+ε)O(n1+ε) time, improving the previous best time bound of O(n4/3+ε)O(n4/3+ε).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 4, May 2015, Pages 360–367
Journal: Computational Geometry - Volume 48, Issue 4, May 2015, Pages 360–367
نویسندگان
Sergio Cabello, Miha Jejčič,