Reconstruction of permutations distorted by single transposition errors

Konstantinova, Elena, Levenshtein, Vladimir and Siemons, Johannes (2007) Reconstruction of permutations distorted by single transposition errors. Proceedings ISIT 2007.

[thumbnail of Reconstruction_of_permutations_distorted_by_single_transposition_errors-2007.pdf]
Preview
PDF (Reconstruction_of_permutations_distorted_by_single_transposition_errors-2007.pdf)
Download (104kB) | Preview

Abstract

— The reconstruction problem for permutations on n elements from their erroneous patterns which are distorted by transpositions is presented in this paper. It is shown that for any n ≥ 3 an unknown permutation is uniquely reconstructible from 4 distinct permutations at transposition distance at most one from the unknown permutation. The transposition distance between two permutations is defined as the least number of transpositions needed to transform one into the other. The proposed approach is based on the investigation of structural properties of a corresponding Cayley graph. In the case of at most two transposition errors it is shown that 3/2(n − 2)(n + 1) distinct erroneous patterns are required in order to reconstruct an unknown permutation. Similar results are obtained for two particular cases when permutations are distorted by given transpositions. These results confirm some bounds for regular graphs which are also presented in this paper

Item Type: Article
Faculty \ School: Faculty of Science > School of Mathematics
UEA Research Groups: Faculty of Science > Research Groups > Algebra and Combinatorics
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 18 Mar 2011 14:26
Last Modified: 24 May 2023 00:00
URI: https://ueaeprints.uea.ac.uk/id/eprint/21024
DOI:

Actions (login required)

View Item View Item