کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430099 | 687798 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate shortest paths in weighted graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present an approximation algorithm for the all pairs shortest paths (APSP) problem in weighed graphs. Our algorithm solves the APSP problem for weighted directed graphs, with real (positive or negative) weights, up to an additive error of ϵ . For any pair of vertices u,vu,v, the algorithm finds a path whose length is at most δ(u,v)+ϵδ(u,v)+ϵ. The algorithm is randomized and runs in O˜(n(ω+3)/2)
► We design an approximation algorithm for the APSP problem in weighted digraphs.
► The approximation guarantee is ϵ -additive.
► The weights may be positive and negative reals with absolute value no(1)no(1).
► The algorithm is randomized and runs in O(n2.688)O(n2.688) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 632–637
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 632–637
نویسندگان
Raphael Yuster,