Предлагается алгоритм сортировки перестановки на основе её множеств круговых инверсий. Указывается на приложения в молекулярной биологии и в теории групп подстановок.
Скачать электронную версию публикации
Загружен, раз: 310
- Title Круговые инверсии перестановок и их использование в задачах сортировки
- Headline Круговые инверсии перестановок и их использование в задачах сортировки
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(31)
- Date:
- DOI
Ключевые слова
diameter of the permutation group, sorting linear and circular permutations, circular inversions of permutations, inversions, диаметр группы подстановок, сортировка линейных и круговых перестановок, инверсии и круговые инверсии перестановокАвторы
Ссылки
Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы // Кибернетика. 1971. №5. С. 33-39.
Глушков В. М. О полноте систем операций в электронных вычислительных машинах // Кибернетика. 1968. №2. С. 1-5.
Зубов А. Ю. О некоторых классах экстремальных ориентированных графов // Прикладная дискретная математика. 2015. №4(30). С. 45-50.
Зубов А. Ю. О представлении подстановок в виде произведений транспозиции и полного цикла // Фундаментальная и прикладная математика. 2009. Т. 15. Вып. 1. С. 31-52.
Зубов А. Ю. О диаметре группы Sn относительно системы образующих, состоящей из полного цикла и транспозиции // Труды по дискретной математике. Т. 2. М.: ТВП, 1998. С.112-150.
Глухов М. М., Погорелов Б. А. О некоторых применениях групп в криптографии // Материалы конф. «Математика и безопасность информационных технологий», МГУ, 28-29 октября 2004г. М.: МЦНМО, 2005. С. 19-31.
Глухов М.М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих // Математические вопросы кибернетики. Вып. 8. М.: Наука, 1999. С. 5-32.
Labarre A. Lower bounding edit distances between permutations // SIAM J. Discr. Math. 2013. Vol.27. No. 3. P. 1410-1428.
Bulteau L., Fertin G., and Rusu I. Sorting by transpositions is difficult // SIAM J. Discr. Math. 2012. Vol.26. No. 12. P. 1148-1180.
Feng J. and Zhu D. Faster algorithms for sorting by transpositions and sorting by block interchanges // ACM Transactions on Algorithms (TALG). 2007. Vol. 3. No. 3. Article No. 25.
Hartman T. and Shamir R. A simpler and faster 1.5-approximation algorithm for sorting by transpositions // Information and Computation. 2006. Vol. 204. P. 275-290.
Cranston D., Sudborough I. H., and West D. B. Short proofs for cat-and-paste sorting of permutations // Discr. Math. 2007. Vol.307. Iss.22. P.2866-2870.
Lin Y. C., Lu C. L., Chang H.-Y., and Tang C. Y. An efficient algorithm for sorting by block-interchanges and its application to the evolution of Vibrio Species // J. Computational Biology. 2005. Vol. 12. No. 1. P. 102-112.
Eriksen N. Combinatorial methods in comparative genomics. Doctoral dissertation. Royal Institute of Technology. Stockholm, 2003. 138 p.
Dias U. and Meidanis J. Sorting by prefix transpositions // String Processing and Information Retrieval. Springer, 2002. P. 65-76.
Eriksson H., Eriksson K., Karlander J., et al. Sorting a bridge hand // Discr. Math. 2001. Vol. 241. No. 1. P. 289-300.
Caprara A. Sorting permutations by reversals and Eulerian cycle decompositions // SIAM J. Discr. Math. 1999. No. 12. P. 91-110.
Heath L. S. and Vergara J. P. C. Sorting by short block-moves // Technical Report TR-98-03. Virginia Tech. Department of Computer Science, Feb. 1998.
Pevzner P. A. and Waterman M. S. Open combinatorial problems in computational molecular biology // Proc. 3rd Israel Symposium on the Theory of Computing and Systems. 1995. P. 158-173.
Kececioglu J. D. and Ravi R. Of mice and men: algorithms for evolutionary distances between genomes with translocation // Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA, USA, 1996. P. 604-613.
Christie D. A. Sorting permutations by block-interchanges // Inform. Proc. Lett. 1996. Vol. 60. No.4. P. 165-169.
Christie D. A. Genome rearrangement problems. Submitted for the degree of Doctor of Philosophy to the University of Glasgow. Glasgow, 1998. 165 p.
Bafna V. and Pevzner P. A. Genome rearrangement and sorting by reversals // SIAM J. Comput. 1996. Vol.25. No. 2. P. 272-289.
Bafna V. and Pevzner P. A. Sorting by transpositions // SIAM J. Discr. Math. 1998. Vol. 11. No. 2. P. 224-240.
Dobzhansky T. and Sturtevant A. H. Inversions in the chromosomes of drosophila pseudoobscura // Genetics. 1938. Vol. 23. P. 28-64.
Aigner M. and West D. B. Sorting by insertion of leading elements // J. Combinatorial Theory. Ser.A. 1987. Vol.45. No.2. P.306-309.
Круговые инверсии перестановок и их использование в задачах сортировки | Прикладная дискретная математика. 2016. № 1(31).