کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414771 | 681033 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An optimal greedy routing algorithm for triangulated polygons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An optimal greedy routing algorithm for triangulated polygons An optimal greedy routing algorithm for triangulated polygons](/preview/png/414771.png)
چکیده انگلیسی
In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 640–647
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 640–647
نویسندگان
Omkar Kulkarni, Huaming Zhang,