• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications(ICCSA 2006) pt.5; 20060508-11; Glasgow(GB) >A CGM Algorithm Solving the Longest Increasing Subsequence Problem
【24h】

A CGM Algorithm Solving the Longest Increasing Subsequence Problem

机译：解决最长增长子序列问题的CGM算法

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

摘要

In this paper, we consider parallel algorithm for the longest increasing subsequence problem. Although this problem is primitive combinatorial optimization problem, this is not known to be in the class NC or P-complete, that is, no NC algorithm have been proposed for this problem, and there is no proof which shows the problem is P-complete. We present a coarse grained parallel algorithm that solves the Longest Increasing Subsequence Problem shown as a basis for DNA comparison. It can be implemented in the CGM model with P processors in O(N log_2 N/P) time and O(P) communication steps for an input sequence of N integers. This algorithm is based on a new optimal and very simple sequential algorithm having a time complexity of O(N log_2 N).
机译：在本文中，我们考虑了最长增长子序列问题的并行算法。尽管此问题是原始组合优化问题，但尚不属于NC或P-complete类，也就是说，尚未针对该问题提出NC算法，也没有证据表明该问题为P-complete。 。我们提出了一种粗粒度并行算法，该算法解决了最长增长子序列问题，该问题被显示为DNA比较的基础。可以在CGM模型中用P个处理器在O（N log_2 N / P）时间和O（P）通信步骤中对N个整数的输入序列中实现。该算法基于时间复杂度为O（N log_2 N）的新的最佳且非常简单的顺序算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号