کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327424 | 681040 | 2013 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stable Roommates Spanner
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We introduce a new geometric spanner whose construction is based on a generalization of the known Stable Roommates problem. The Stable Roommates Spanner combines the most desirable properties of geometric spanners: a natural definition, small degree, linear number of edges, strong (1+ϵ)-spanner for every ϵ>0, and an efficient construction algorithm. It is an improvement over the well-known Yao graph and Î-graph and their variants. We show how to construct such a spanner for a set of points in the plane in O(nlog10n) expected time. We introduce a variant of the Stable Roommates Spanner called the Stable Roommates Î-Spanner which we can generalize to higher dimensions and construct more efficiently in O(nlogdn) time. This variant possesses all the properties of the Stable Roommates Spanner except that it is no longer a strong spanner.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 2, February 2013, Pages 120-130
Journal: Computational Geometry - Volume 46, Issue 2, February 2013, Pages 120-130
نویسندگان
Prosenjit Bose, Paz Carmi, Lilach Chaitman-Yerushalmi, Sébastien Collette, Matthew J. Katz, Stefan Langerman,