کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650795 1632441 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On reconstruction of signed permutations distorted by reversal errors
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On reconstruction of signed permutations distorted by reversal errors
چکیده انگلیسی

The problem of reconstructing signed permutations on n   elements from their erroneous patterns distorted by reversal errors is considered in this paper. A reversal is the operation of taking a segment of the signed permutation, reversing it, and flipping the signs of its elements. The reversal metric is defined as the least number of reversals transforming one signed permutation into another. It is proved that for any n⩾2n⩾2 an arbitrary signed permutation is uniquely reconstructible from three distinct signed permutations at reversal distance at most one from the signed permutation. The proposed approach is based on the investigation of structural properties of a Cayley graph G2nG2n whose vertices form a subgroup of the symmetric group Sym2nSym2n. It is also proved that an arbitrary signed permutation is reconstructible from two distinct signed permutations with probability p2∼13 as n→∞n→∞. In the case of at most two reversal errors it is shown that at least n(n+1)n(n+1) distinct erroneous patterns are required in order to reconstruct an arbitrary signed permutation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issues 5–6, 28 March 2008, Pages 974–984
نویسندگان
,