کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431279 | 688494 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The lexicographically smallest universal cycle for binary strings with minimum specified weight
ترجمه فارسی عنوان
کمترین چرخه ی جهانی برای رشته های دودویی با حداقل وزن مشخصی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
H. Fredricksen, I.J. Kessler and J. Maiorana discovered a simple but elegant construction of a universal cycle for binary strings of length n: Concatenate the aperiodic prefixes of length n binary necklaces in lexicographic order. We generalize their construction to binary strings of length n whose weights are in the range c,c+1,…,nc,c+1,…,n by simply omitting the necklaces with weight less than c . We also provide an efficient algorithm that generates the universal cycles in constant amortized time per bit using O(n)O(n) space. Our universal cycles have the property of being the lexicographically smallest universal cycle for the set of binary strings of length n with weight ≥c.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 28, September 2014, Pages 31–40
Journal: Journal of Discrete Algorithms - Volume 28, September 2014, Pages 31–40
نویسندگان
Joe Sawada, Aaron Williams, Dennis Wong,