Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871645 | Discrete Applied Mathematics | 2018 | 22 Pages |
Abstract
The recurrence formula is built based on the analysis of the probability that two nodes of the breakpoint graph belong to the same alternating cycle among all the breakpoint graphs related with permutations of length n. Through this analysis it is possible to compute the average reversal distance for signed variations of the identity permutation. Also, lower and upper bounds of the average reversal distance for signed permutations are provided. Additionally, based on computational data, it is shown how these bounds can be used in order to propose concrete upper and lower bounds.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Thaynara Arielly de Lima, Mauricio Ayala-Rincón,