On The Diameter Of Rearrangement Problems

dc.creatorLintzmayer C.N.
dc.creatorDias Z.
dc.date2014
dc.date2015-06-25T18:03:15Z
dc.date2015-11-26T15:05:43Z
dc.date2015-06-25T18:03:15Z
dc.date2015-11-26T15:05:43Z
dc.date.accessioned2018-03-28T22:16:18Z
dc.date.available2018-03-28T22:16:18Z
dc.identifier9783319079523
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). Springer Verlag, v. 8542 LNBI, n. , p. 158 - 170, 2014.
dc.identifier3029743
dc.identifier10.1007/978-3-319-07953-0_13
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84903941599&partnerID=40&md5=87f0ff3185ff72617873163af919ab30
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/88012
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/88012
dc.identifier2-s2.0-84903941599
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1257096
dc.descriptionWhen we consider the Genome Rearrangements area, the problems of finding the distance of a permutation and finding the diameter of all permutations of the same size are the most common studied. In this paper, we considered problems for which no known results were presented regarding their diameters. We present some families of permutations whose distance is identical to the diameter for small sizes. They allowed us to gave bounds for the diameters of the problems we considered, as well as conjectures regarding the exact value. © 2014 Springer International Publishing.
dc.description8542 LNBI
dc.description
dc.description158
dc.description170
dc.descriptionBafna, V., Pevzner, P.A., Genome Rearrangements and Sorting by Reversals (1993) Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pp. 148-157
dc.descriptionBulteau, L., Fertin, G., Rusu, I., Pancake Flipping is Hard (2012) LNCS, 7464, pp. 247-258. , Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. Springer, Heidelberg
dc.descriptionBulteau, L., Fertin, G., Rusu, I., Sorting by Transpositions is Difficult (2012) SIAM Journal on Computing, 26 (3), pp. 1148-1180
dc.descriptionCaprara, A., Sorting Permutations by Reversals and Eulerian Cycle Decompositions (1999) SIAM Journal on Discrete Mathematics, 12 (1), pp. 91-110
dc.descriptionChitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I.H., Voit, W., An (18/11)n Upper Bound for Sorting by Prefix Reversals (2009) Theoretical Computer Science, 410 (36), pp. 3372-3390
dc.descriptionChitturi, B., Sudborough, I.H., Bounding Prefix Transposition Distance for Strings and Permutations (2012) Theoretical Computer Science, 421, pp. 15-24
dc.descriptionCibulka, J., On Average and Highest Number of Flips in Pancake Sorting (2011) Theoretical Computer Science, 412 (8-10), pp. 822-834
dc.descriptionDias, Z., Meidanis, J., Sorting by Prefix Transpositions (2002) LNCS, 2476, pp. 65-76. , Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. Springer, Heidelberg
dc.descriptionElias, I., Hartman, T., A 1.375-Approximation Algorithm for Sorting by Transpositions (2006) 375-Approximation Algorithm for Sorting by Transpositions, 3 (4), pp. 369-379
dc.descriptionEriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wastlund, J., Sorting a Bridge Hand (2001) Discrete Mathematics, 241 (1-3), pp. 289-300
dc.descriptionFertin, G., Labarre, A., Rusu, I., Tannier, É., Vialette, S., Combinatorics of Genome Rearrangements (2009) Computational Molecular Biology, , MIT Press
dc.descriptionGalvão, G.R., Dias, Z., Computing Rearrangement Distance of Every Permutation in the Symmetric Group (2011) Proceedings of the 26th ACM Symposium on Applied Computing (SAC 22011), pp. 106-107. , Chu, W.C., Wong, W.E., Palakal, M.J., Hung, C.C. (eds.) ACM
dc.descriptionGates, W.H., Papadimitriou, C.H., Bounds for Sorting by Prefix Reversal (1979) Discrete Mathematics, 27 (1), pp. 47-57
dc.descriptionHannenhalli, S., Pevzner, P.A., Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals (1999) Journal of the ACM, 46 (1), pp. 1-27
dc.descriptionHeydari, M.H., Sudborough, I.H., On the Diameter of the Pancake Network (1997) Journal of Algorithms, 25 (1), pp. 67-94
dc.descriptionLabarre, A., Edit Distances and Factorisations of Even Permutations (2008) LNCS, 5193, pp. 635-646. , Halperin, D., Mehlhorn, K. (eds.) ESA 2008. Springer, Heidelberg
dc.descriptionLintzmayer, C.N., Dias, Z., On Sorting of Signed Permutations by Prefix and Suffix Reversals and Transpositions (2014) Proceedings of the 1st International Conference on Algorithms for Computational Biology (AlCoB 2014), Tarragona, Spain, pp. 1-12. , Dediu, A.H., Martín-Vide, C., Truthe, B. (eds.) Springer
dc.descriptionLintzmayer, C.N., Dias, Z., Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions (2014) LNCS, 8392, pp. 671-682. , Pardo, A., Viola, A. (eds.) LATIN 2014. Springer, Heidelberg
dc.descriptionMeidanis, J., Walter, M.M.T., Dias, Z., A Lower Bound on the Reversal and Transposition Diameter (2002) Journal of Computational Biology, 9 (5), pp. 743-745
dc.descriptionSharmin, M., Yeasmin, R., Hasan, M., Rahman, A., Rahman, M.S., Pancake Flipping with Two Spatulas (2010) Electronic Notes in Discrete Mathematics, 36, pp. 231-238. , International Symposium on Combinatorial Optimization (ISCO 2010)
dc.descriptionWalter, M.E.M.T., Dias, Z., Meidanis, J., Reversal and Transposition Distance of Linear Chromosomes (1998) Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE 1998), pp. 96-102. , IEEE Computer Society, Santa Cruz
dc.languageen
dc.publisherSpringer Verlag
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleOn The Diameter Of Rearrangement Problems
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución