Listing all sorting reversals in quadratic time |
| |
| Authors: | Krister M Swenson Ghada Badr David Sankoff |
| |
| Institution: | 1.Department of Mathematics and Statistics,University of Ottawa,Ontario,Canada;2.LaCIM, UQAM,Montréal Québec,Canada;3.SITE, School of Information Technology and Engineering, University of Ottawa,Ontario,Canada;4.IRI - Mubarak city for Science and Technology, University and Research District,Alex,Egypt |
| |
| Abstract: | We describe an average-case O(n
2) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to
write the list is Ω(n
2) in the worst case. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
