کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950885 | 1441038 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Source-wise round-trip spanners
ترجمه فارسی عنوان
کلاه گیس دورافتاده منبع معقول
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های گراف، چرخ دنده های گراف اسپیندر تور دور کوتاهترین فاصله،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we study a new type of graph spanners, called source-wise round-trip spanners. Given any source vertex set SâV in a directed graph G(V,E), such a spanner (with stretch k) has the property that the round-trip shortest path distance from any vertex sâS to any vertex vâV is at most k times of their round-trip distance in G. We present an algorithm to construct the source-wise round-trip spanners with stretch (2k+ϵ) and size O((k2/ϵ)ns1/klogâ¡(nw)) where n=|V|,s=|S| and w is the maximum edge weight. The result out-performs the state-of-the-art traditional round-trip spanners when the source vertex set S has small cardinality, and at the same time, it matches the traditional spanners when S is the whole vertex set V.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 124, August 2017, Pages 42-45
Journal: Information Processing Letters - Volume 124, August 2017, Pages 42-45
نویسندگان
Chun Jiang Zhu, Kam-Yiu Lam,