Listing all sorting reversals in quadratic time

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.

Detalles Bibliográficos
Autores principales: Swenson, Krister M, Badr, Ghada, Sankoff, David
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2011
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3110122/
https://www.ncbi.nlm.nih.gov/pubmed/21504604
http://dx.doi.org/10.1186/1748-7188-6-11
_version_ 1782205484619530240
author Swenson, Krister M
Badr, Ghada
Sankoff, David
author_facet Swenson, Krister M
Badr, Ghada
Sankoff, David
author_sort Swenson, Krister M
collection PubMed
description 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.
format Online
Article
Text
id pubmed-3110122
institution National Center for Biotechnology Information
language English
publishDate 2011
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-31101222011-06-08 Listing all sorting reversals in quadratic time Swenson, Krister M Badr, Ghada Sankoff, David Algorithms Mol Biol Research 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. BioMed Central 2011-04-19 /pmc/articles/PMC3110122/ /pubmed/21504604 http://dx.doi.org/10.1186/1748-7188-6-11 Text en Copyright ©2011 Swenson et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Swenson, Krister M
Badr, Ghada
Sankoff, David
Listing all sorting reversals in quadratic time
title Listing all sorting reversals in quadratic time
title_full Listing all sorting reversals in quadratic time
title_fullStr Listing all sorting reversals in quadratic time
title_full_unstemmed Listing all sorting reversals in quadratic time
title_short Listing all sorting reversals in quadratic time
title_sort listing all sorting reversals in quadratic time
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3110122/
https://www.ncbi.nlm.nih.gov/pubmed/21504604
http://dx.doi.org/10.1186/1748-7188-6-11
work_keys_str_mv AT swensonkristerm listingallsortingreversalsinquadratictime
AT badrghada listingallsortingreversalsinquadratictime
AT sankoffdavid listingallsortingreversalsinquadratictime

Ejemplares similares