Reconstruction of permutations distorted by single transposition errors

Details Reconstruction of permutations distorted by single transposition errors Reconstruction of permutations distorted by single transposition errors

2007-02-07

arxiv.org/abs/math/0702191v1

Mathematics

Combinatorics

5 pages, Report of paper presented at ISIT-2007

Scientific paper

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 \geq 3$ an unknown permutation is uniquely reconstructible from 4 distinct permutations at transposition distance at most one from the unknown permutation. The {\it 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 $\frac32(n-2)(n+1)$ 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.

Affiliated with

Also associated with

No associations

Rating

Reconstruction of permutations distorted by single transposition errors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstruction of permutations distorted by single transposition errors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of permutations distorted by single transposition errors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219087