...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >A fast algorithm for multiplying min-sum permutations
【24h】

A fast algorithm for multiplying min-sum permutations

机译：最小和排列相乘的快速算法

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

摘要

The present article considers the problem for determining, for given two permutations over indices from 1 to n, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(~(n1.5)) time, or very recently, in O(nlogn) time. The present article independently proposes another O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices g and i with 1≤g
机译：对于给定的两个从1到n的索引排列，本文考虑了确定其分布矩阵与给定排列的分布矩阵的最小和积相同的排列的问题。这个问题在计算字符串之间的相似度方面有几个应用。迄今为止，解决该问题最快的已知算法是在O（〜（n1.5））时间或最近在O（nlogn）时间执行。本文针对相同的问题独立提出了另一种O（nlogn）时间算法，对于给定的索引g和i，其中1≤g

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号