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

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
نویسندگان
, ,