کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952436 | 1442034 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Space-efficient path-reporting approximate distance oracles
ترجمه فارسی عنوان
فضایی کارآمد مسیر گزارش فاصله تقریبی اوراکل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider approximate path-reporting distance oracles, distance labeling and labeled routing with extremely low space requirements, for general undirected graphs. For distance oracles, we show how to break the nlogâ¡n space bound of Thorup and Zwick if approximate paths rather than distances need to be reported. For approximate distance labeling and labeled routing, we break the previously best known space bound of O(logâ¡n) words per vertex. The cost for such space efficiency is an increased stretch.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 1-10
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 1-10
نویسندگان
Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen,