On the Diameter of Rearrangement Problems

详细信息    查看全文

• 作者：Carla Negri Lintzmayer (20)
  Zanoni Dias (20)
  
• 关键词：Sorting permutations ; diameter ; reversals ; transpositions ; prefix operations ; suffix operations
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8542
• 期：1
• 页码：158-170
• 参考文献：1. Bafna, V., Pevzner, P.A.: Genome Rearrangements and Sorting by Reversals. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pp. 148鈥?57 (1993)
  2. Bulteau, L., Fertin, G., Rusu, I.: Pancake Flipping is Hard. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.聽7464, pp. 247鈥?58. Springer, Heidelberg (2012) CrossRef
  3. Bulteau, L., Fertin, G., Rusu, I.: Sorting by Transpositions is Difficult. SIAM Journal on Computing聽26(3), 1148鈥?180 (2012)
  4. Caprara, A.: Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM Journal on Discrete Mathematics聽12(1), 91鈥?10 (1999) CrossRef
  5. Chitturi, 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. Theoretical Computer Science聽410(36), 3372鈥?390 (2009) CrossRef
  6. Chitturi, B., Sudborough, I.H.: Bounding Prefix Transposition Distance for Strings and Permutations. Theoretical Computer Science聽421, 15鈥?4 (2012) CrossRef
  7. Cibulka, J.: On Average and Highest Number of Flips in Pancake Sorting. Theoretical Computer Science聽412(8-10), 822鈥?34 (2011) CrossRef
  8. Dias, Z., Meidanis, J.: Sorting by Prefix Transpositions. In: Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. LNCS, vol.聽2476, pp. 65鈥?6. Springer, Heidelberg (2002) CrossRef
  9. Elias, I., Hartman, T.: A 1.375-Approximation Algorithm for Sorting by Transpositions. 375-Approximation Algorithm for Sorting by Transpositions聽3(4), 369鈥?79 (2006)
  10. Eriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wastlund, J.: Sorting a Bridge Hand. Discrete Mathematics聽241(1-3), 289鈥?00 (2001) CrossRef
  11. Fertin, G., Labarre, A., Rusu, I., Tannier, 脡., Vialette, S.: Combinatorics of Genome Rearrangements. In: Computational Molecular Biology. MIT Press (2009)
  12. Galv茫o, G.R., Dias, Z.: Computing Rearrangement Distance of Every Permutation in the Symmetric Group. In: Chu, W.C., Wong, W.E., Palakal, M.J., Hung, C.C. (eds.) Proceedings of the 26th ACM Symposium on Applied Computing (SAC 22011), pp. 106鈥?07. ACM (2011)
  13. Gates, W.H., Papadimitriou, C.H.: Bounds for Sorting by Prefix Reversal. Discrete Mathematics聽27(1), 47鈥?7 (1979) CrossRef
  14. Hannenhalli, S., Pevzner, P.A.: Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals. Journal of the ACM聽46(1), 1鈥?7 (1999) CrossRef
  15. Heydari, M.H., Sudborough, I.H.: On the Diameter of the Pancake Network. Journal of Algorithms聽25(1), 67鈥?4 (1997) CrossRef
  16. Labarre, A.: Edit Distances and Factorisations of Even Permutations. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.聽5193, pp. 635鈥?46. Springer, Heidelberg (2008) CrossRef
  17. Lintzmayer, C.N., Dias, Z.: On Sorting of Signed Permutations by Prefix and Suffix Reversals and Transpositions. In: Dediu, A.H., Mart铆n-Vide, C., Truthe, B. (eds.) Proceedings of the 1st International Conference on Algorithms for Computational Biology (AlCoB 2014), Tarragona, Spain, pp. 1鈥?2. Springer (2014)
  18. Lintzmayer, C.N., Dias, Z.: Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol.聽8392, pp. 671鈥?82. Springer, Heidelberg (2014) CrossRef
  19. Meidanis, J., Walter, M.M.T., Dias, Z.: A Lower Bound on the Reversal and Transposition Diameter. Journal of Computational Biology聽9(5), 743鈥?45 (2002) CrossRef
  20. Sharmin, M., Yeasmin, R., Hasan, M., Rahman, A., Rahman, M.S.: Pancake Flipping with Two Spatulas. In: International Symposium on Combinatorial Optimization (ISCO 2010). Electronic Notes in Discrete Mathematics, vol.聽36, pp. 231鈥?38 (2010)
  21. Walter, M.E.M.T., Dias, Z., Meidanis, J.: Reversal and Transposition Distance of Linear Chromosomes. In: Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE 1998), pp. 96鈥?02. IEEE Computer Society, Santa Cruz (1998)
  
• 作者单位：Carla Negri Lintzmayer (20)
  Zanoni Dias (20)
  
  20. Institute of Computing, University of Campinas (Unicamp), Av. Albert Einstein, 1251, Campinas, S茫o Paulo, Brazil
  
• ISSN：1611-3349

文摘

When 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.