کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431085 | 688270 | 2010 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies](/preview/png/431085.png)
چکیده انگلیسی
Given a geometric graph G=(S,E)G=(S,E) in RdRd with constant dilation t, and a positive constant ε , we show how to construct a (1+ε)(1+ε)-spanner of G with O(|S|)O(|S|) edges using O(sort(|E|))O(sort(|E|)) memory transfers in the cache-oblivious model of computation. The main building block of our algorithm, and of independent interest in itself, is a new cache-oblivious algorithm for constructing a well-separated pair decomposition which builds such a data structure for a given point set S⊂RdS⊂Rd using O(sort(|S|))O(sort(|S|)) memory transfers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 8, Issue 3, September 2010, Pages 259–272
Journal: Journal of Discrete Algorithms - Volume 8, Issue 3, September 2010, Pages 259–272
نویسندگان
Fabian Gieseke, Joachim Gudmundsson, Jan Vahrenhold,