A simple framework on sorting permutations
From MaRDI portal
Publication:6259482
arXiv1502.07971MaRDI QIDQ6259482FDOQ6259482
Authors: Ricky X. F. Chen, Christian M. Reidys 
Publication date: 27 February 2015
Abstract: In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.
This page was built for publication: A simple framework on sorting permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6259482)
