کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420310 | 683921 | 2006 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Randomized vs. deterministic distance query strategies for point location on the line
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Randomized vs. deterministic distance query strategies for point location on the line Randomized vs. deterministic distance query strategies for point location on the line](/preview/png/420310.png)
چکیده انگلیسی
Suppose that nn points are located at nn mutually distinct but unknown positions on the line, and we can measure their pairwise distances. How many measurements are needed to determine their relative positions uniquely? The problem is motivated by DNA mapping techniques based on pairwise distance measures. It is also interesting by itself for its own and surprisingly deep. Continuing our earlier work on this problem, we give a simple randomized two-round strategy that needs, with high probability, only (1+o(1))n(1+o(1))n measurements. We show that deterministic strategies cannot manage the task in two rounds with (1+o(1))n(1+o(1))n measurements in the worst case. We improve an earlier deterministic bound to roughly 4n/34n/3 measurements.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 3, 1 March 2006, Pages 478–484
Journal: Discrete Applied Mathematics - Volume 154, Issue 3, 1 March 2006, Pages 478–484
نویسندگان
Peter Damaschke,