• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Algebraic Biology(AB 2007); 20070702-04; Castle of Hagenberg(AT) >Prefix Reversals on Binary and Ternary Strings
【24h】

Prefix Reversals on Binary and Ternary Strings

机译：二进制和三进制字符串的前缀反转

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given a permutation n, the application of prefix reversal f~((i)) to n reverses the order of the first i elements of π. The problem of Sorting By Prefix Reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (Bounds for sorting by prefix reversal, Discrete Mathematics 27, pp. 47-57), asks for the minimum number of prefix reversals required to sort the elements of a given permutation. In this paper we study a variant of this problem where the prefix reversals act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix reversals required to sort binary and ternary strings, with polynomial-time algorithms for these sorting problems as a resu demonstrate that computing the minimum prefix reversal distance between two binary strings is NP-hard; give an exact expression for the prefix reversal diameter of binary strings, and give bounds on the prefix reversal diameter of ternary strings. We also consider a weaker form of sorting called grouping (of identical symbols) and give polynomial-time algorithms for optimally grouping binary and ternary strings. A number of intriguing open problems are also discussed.
机译：给定一个排列n，将前缀反转f〜（（i））应用于n会反转π的前i个元素的顺序。盖茨和帕帕迪米特里乌着名的前缀反转排序问题（又称煎饼翻转）（按前缀反转排序的界限，离散数学27，第47-57页），要求为对给定排列的元素进行排序。在本文中，我们研究了此问题的变体，其中前缀反转不作用于排列，而是作用于固定大小的字母上的字符串。我们确定排序二进制和三进制字符串所需的最小前缀反转次数，并使用多项式时间算法来解决这些排序问题。证明计算两个二进制字符串之间的最小前缀反转距离是NP-hard的；给出二进制字符串的前缀反转直径的精确表达式，并给出三进制字符串的前缀反转直径的界限。我们还考虑了一种称为“分组（相同符号）”的较弱的排序形式，并给出了多项式时间算法来对二进制和三进制字符串进行最佳分组。还讨论了许多有趣的开放问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号