کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414236 | 680855 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sequential dependency computation via geometric data structures
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We are given integers 0⩽G1⩽G2≠00⩽G1⩽G2≠0 and a sequence Sn=〈a1,a2,…,an〉Sn=〈a1,a2,…,an〉 of n integers. The goal is to compute the minimum number of insertions and deletions necessary to transform SnSn into a valid sequence, where a sequence is valid if it is nonempty, all elements are integers, and all the differences between consecutive elements are between G1G1 and G2G2. For this problem from the database theory literature, previous dynamic programming algorithms have running times O(n2)O(n2) and O(A⋅nlogn), for a parameter A unrelated to n . We use a geometric data structure to obtain a O(nlognloglogn) running time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 141–148
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 141–148
نویسندگان
Gruia Calinescu, Howard Karloff,