کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868464 | 1439978 | 2018 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cone-based spanners of constant degree
ترجمه فارسی عنوان
جرثقیل بر اساس مخروط درجه ثابت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study spanning properties of sparse cone-based graphs of constant degree, parameterized by a positive integer k>1. Cone-based graphs partition the space around each vertex into k equiangular cones, and select at most one outgoing edge in each cone. This guarantees an out-degree of at most k, but the in-degree may be unbounded. To bound the in-degree, at most one incoming edge is retained in each cone. This yields a sparse graph of degree at most 2k (in-degree k and out-degree k). In this paper we introduce the notion of canonical k-cone graphs and establish a spanning ratio of 16.76 for this class of graphs, provided that k=6kâ² and kâ²â¥5. The spanning ratio decreases to 4.64 as kâ² increases to 8. We show that both Yao-Yao and Theta-Theta graphs are canonical k-cone graphs and therefore they inherit these spanning ratios. Yao-Yao and Theta-Theta graphs differ only in the way edges are selected. Yao-Yao graphs select an edge of minimum Euclidean length, whereas Theta-Theta graphs select an edge of minimum orthogonal projection onto the cone bisector.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 48-61
Journal: Computational Geometry - Volume 68, March 2018, Pages 48-61
نویسندگان
Mirela Damian,