id: 05235186
dt: j
an: 05235186
au: Konstantinova, Elena
ti: On reconstruction of signed permutations distorted by reversal errors.
so: Discrete Math. 308, No. 5-6, 974-984 (2008).
py: 2008
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: reconstruction of signed permutations; Cayley graphs; sorting by reversals;
    reversal metric
ci: Zbl 1126.05006
li: doi:10.1016/j.disc.2007.08.003
ab: The author extends the study of whether permutations distorted by a single
    reversal error can be reconstructed [Discrete Appl. Math. 155,
    2426-2434 (2007; Zbl 1126.05006)] to signed permutations. Reversals
    take a substring of the signed permutation, reverse it, and switch the
    signs of its elements. For a signed permutation $P$, let $B_r(P)$ be
    the set of all signed permutations arising from $P$ by $r$ reversals.
    It is proved, that for any $P\in B_n$ with $n\ge2$ the minimal number
    of signed permutations in $B_1(P)$ which are sufficient to reconstruct
    $P$ is equal to 3. Furthermore it is shown, that $P$ is reconstructible
    from two signed permutations in $B_1(P)$ with a probability
    $\sim\frac{1}{3}$ if $n\to\infty$. In case of at most two reversal
    errors, it is proved that at least $n(n+1)$ permutations in $B_2(P)$
    are required for reconstructing $P$. The approach is based on the
    structure of Cayley graphs.
rv: Astrid Reifegerste (Magdeburg)