Reconstruction of permutations distorted by single transposition errors

MaRDI QIDQ6478739zbMATH OpenFDO

Authors Elena V. Konstantinova, Vladimir Levenshtein, Johannes Siemons

Publication date 7 February 2007

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Association schemes, strongly regular graphs (05E30)

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 $ngeq3$ 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.

This page was built for publication: Reconstruction of permutations distorted by single transposition errors

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