کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431279 688494 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The lexicographically smallest universal cycle for binary strings with minimum specified weight
ترجمه فارسی عنوان
کمترین چرخه ی جهانی برای رشته های دودویی با حداقل وزن مشخصی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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