On reconstruction of signed permutations distorted by reversal errors

DOI10.1016/J.DISC.2007.08.003MaRDI QIDQ2470469zbMATH OpenOpenAlexFDO

Authors Elena V. Konstantinova

Publication date 14 February 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.08.003

zbMATH Keywords

Cayley graphsreconstruction of signed permutationsreversal metricsorting by reversals

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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\geq2\) 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.

Recommendations

• Reconstruction of permutations distorted by reversal errors
• Reconstruction of permutations from their erroneous patterns
• SORTING SIGNED PERMUTATIONS BY FIXED-LENGTH REVERSALS
• Sorting signed permutations by reversals, revisited
• On the average number of reversals needed to sort signed permutations

Cites work

• Efficient reconstruction of sequences
• Efficient reconstruction of sequences from their subsequences of supersequences
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• Reconstruction of objects from a minimum number of distorted patterns
• Reconstruction of permutations distorted by reversal errors

Cited in

(11)

• Vertex reconstruction in Cayley graphs
• Error graphs and the reconstruction of elements in groups
• Reconstruction of permutations distorted by reversal errors
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
• Reconstruction of permutations from their erroneous patterns
• Reconstruction of permutations distorted by single Kendall -errors
• Balanced reconstruction codes for single edits
• The sequence reconstruction problem for permutations with the Hamming distance
• The sequence reconstruction of permutations with Hamming metric
• Some problems on Cayley graphs

This page was built for publication: On reconstruction of signed permutations distorted by reversal errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2470469)