کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
414538 680974 2016 7 صفحه PDF سفارش دهید دانلود رایگان
عنوان انگلیسی مقاله ISI
Analysis of farthest point sampling for approximating geodesics in a graph
ترجمه فارسی عنوان
تجزیه و تحلیل از نمونه برداری دورترین نقطه برای تخمین ژئودزیک در یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
کلمات کلیدی
نمونه برداری دورترین نقطه ؛ ژئودزیک تقریبی؛ کوتاهترین مسیرها؛ نمودار مسطح؛ الگوریتم های تقریبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources.In this paper, we analyze the stretch factor FFPSFFPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that FFPSFFPS can be bounded in terms of the minimal value F⁎F⁎ of the stretch factor obtained using an optimal placement of k   sources as FFPS⩽2re2F⁎+2re2+8re+1, where rere is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor rere is not an artefact of the analysis by providing a class of graphs for which FFPS⩾12reF⁎.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 57, August 2016, Pages 1–7
نویسندگان
, , , ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت